怎么感觉这题能贪?
查看原帖
怎么感觉这题能贪?
1219462
Ratio_Y楼主2024/7/22 11:23

rt,随到这题,然后随便打个贪心过了。思路就是先找面值大的往小了枚举,代码如下:

int n,k,ans=1e9;
int a[N];
namespace Wisadel
{
	short main()
	{
		// freopen("1.in","r",stdin),freopen("1.out","w",stdout);
		n=qr,k=qr;
		fo(i,1,n) a[i]=qr;
		sort(a+1,a+1+n);
		fu(i,n,1)
		{
			int sum=0,now=i,anss=0;
			while(sum<k)
			{
				if(sum+a[now]<=k) anss++,sum+=a[now];
				else now--;
				if(!now)
				{
					anss=1e9;
					break;
				}
			}
			ans=min(anss,ans);
		}
		printf("%d\n",ans);
		return Ratio;
	}
}
int main(){return Wisadel::main();}
2024/7/22 11:23
加载中...