社区讨论

贪心75哪错了...

P3052[USACO12MAR] Cows in a Skyscraper G参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lodhe8r2
此快照首次捕获于
2023/10/31 06:38
2 年前
此快照最后确认于
2023/11/06 21:51
2 年前
查看原帖
怎么也举不出反例啊...
而且最后一个数据点我输出的是1,expected 9 怎么想都不对啊
CPP
#include<iostream>
#include<cstring>
#include<algorithm>
using std::cin;
using std::cout;
const int N=18;
#define reint register int
int n,w,val[N],k,ans;
bool vis[N];
inline bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n>>w;
	memset(vis,false,sizeof(vis));
	for(reint i=1;i<=n;++i)
	cin>>val[i];
	std::sort(val+1,val+1+n,cmp);
	for(reint i=1;i<=n;++i)
	{
		if(vis[i])continue;
		++ans;
		int nows=val[i];
		for(reint j=i+1;j<=n;++j)
		{
			if(vis[j]||nows+val[j]>w)continue;
			nows+=val[j];
			vis[j]=true;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...