Codeforces Round #760 (Div. 3) D. Array and Operations

Problem - D - Codeforces

题意：

给定一个数组，每次操作选取两个数，贡献加上a[i]/[j]（向下取整），最多执行k次操作，k次操作完了之后把剩下所有数都加入贡献，问你最小贡献是什么

思路：

不知道为什么标签里会有一个dp....，这道题就是贪心+操作

首先注意到k次操作完了之后把剩下的数都加到贡献里面，显然要让剩下的数尽可能小，那就是对数组中最大的2*k个数进行操作了，要让a[i]/a[j]（向下取整）尽可能小，就让a[i]<=a[j]，那么贡献就是0或1

一开始想的是把所有数都排序去重，然后写个循环模拟，后来发现不好处理

正确的处理方式取第k+i个和第k个相除即可

Code：

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e2+10;
int n,k,ans=0;
int a[mxn];
bool cmp(int x,int y){
	return x>y;
}
void solve(){
	ans=0;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=k;i++){
		ans+=a[k+i]/a[i];
	}
	for(int i=2*k+1;i<=n;i++) ans+=a[i];
	printf("%d\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

总结：

这道题的贪心思想一定是这样的，不能因为难以实现就去怀疑贪心策略，应该去想怎么正确处理来的方便