cf--contest1326:C. Permutation Partitions+推理

傳送門

C. Permutation Partitions

題意

給出一個長度為n的數組，裡面包含[1,n]所有的數，在給定一個整數k，将數組k分成k個集合，要讓每個集合中最大值的和最大化。求出這個最大值的和，還有求出有幾種分法，由于方法的總數可能很大，對其進行取模998244353 處理？

思路

1.對原來的數組排序，然後取出前k大的值，前k值的和就是第一個答案

2.标記前k大值在原有數組中的位置，計算出相鄰之間的距離相乘即可，這個可用數學歸納法得出。

假設标記了3個數在不同的位置

2 7 3 1 5 4 6

{[1,2],[3,5],[6,7]} ,{[1,2],[3,6],[7,7]},

{[1,3],[4,5],[6,7]}, {[1,3],[4,6],[7,7]},

{[1,4],[5,5],[6,7]}, {[1,4],[5,6],[7,7]}。

可以發現一個規律

包含7的有3種可能[1,2],[1,3],[1,7];

包含5的有2種可能[5,5],[5,6];

最後一個被唯一确定。

那麼組合就有2*3=6種。

AC代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=200005;
const ll Mod=998244353;

bool vis[MAXN];
int a[MAXN],b[MAXN];

bool cmp(int a,int b){
	return a>b;
}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(a+1,a+n+1,cmp);
	ll ans=0,res=1;
	int pos=0;
	for(int i=1;i<=k;i++)	vis[a[i]]=true,ans=(ll)ans+a[i];
	bool flag=true;
	for(int i=1;i<=n;i++){
		if(vis[b[i]] && !flag){
			res=res*(i-pos)%Mod;
			pos=i;
		}
		if(vis[b[i]] && flag){
			pos=i;
			flag=false;
		}
	}
	printf("%lld %lld",ans,res);
	return 0;
}