Codeforces 1114B (贪心)

题面

传送门

分析

答案很好看出，显然是选最大的m*k个数

那么如何构造方案呢

我们把最大的m*k个数的位置标记为1，其他标记为0

从左到右维护一个ptr，记录有标记的数的个数，如果当前有m个有标记的数，则已经找到一个满足条件的区间分界点，break

这样的操作进行k-1次,由于ptr单调递增，时间复杂度为\(O(n)\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<map>

#include<algorithm>

#define maxn 200005

using namespace std;

typedef long long ll;

int n,m,k;

struct node{

	int x;

	int id;

}a[maxn];

int mark[maxn];

int cmp(node a,node b){

	return a.x>b.x;

}

vector<int>res;

map<int,int>cnt;

int main(){

	scanf("%d %d %d",&n,&m,&k);

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i].x);

		a[i].id=i;

	}

	sort(a+1,a+1+n,cmp);

	ll ans=0;

	for(int i=1;i<=m*k;i++){

		ans+=a[i].x;

		mark[a[i].id]=1;

	}

	int ptr=1;

	for(int i=1;i<k;i++){

		int len=0;

		while(ptr<=n){

			if(mark[ptr]){

				len++;

			}

			if(len==m) break;

			ptr++;

		}

		res.push_back(ptr);

		ptr++;

	}

	printf("%lld\n",ans);

	for(int x : res){

		printf("%d ",x);

	}

}

巴特西

Codeforces 1114B (贪心)

题面

分析

代码

最新文章

热门文章