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;
}