关于贪心
查看原帖
关于贪心
501923
duchengjun楼主2023/9/2 10:55

本蒟蒻觉得贪心没有问题啊但是WA60pts,代码贴在下面:

#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>

using namespace std;

const int N=3000+10;

int n,k;
int a[N];

int main(){
	
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	if(a[k]==120){
		printf("You can't do it.\n");
		return 0;
	}
	int l=1,r=k,cnt=0;
	while(l<r&&a[r]==119){
		r--;
		cnt++;
	}
	while(l<r&&a[l]+a[r]>119){
		r--;
		cnt++;
	}
	while(l<=r){
		int tmp=119-a[r],ans=0;
		while(ans<=tmp&&l<r){
			ans+=a[l];
			l++;
		}
		if(ans>tmp)
			l--;
		cnt++;
		r--;
	}
	printf("%d\n",cnt);
	return 0;
	
}

2023/9/2 10:55
加载中...