526互联

AtCoder Beginner Contest 317 D - President

发布时间 2023-09-01 22:16:16作者: 无上大宗师

D - President

原题链接


题意：一共n轮，每一轮Xi > Yi （票数）时，X可以获得Zi 张席位，反之亦然；最终席位总和多的就获胜；因此要使X获胜，求Y至少要给X多少个票

思路：

数据范围小，Z的和小于1e5

可以用01背包的方法,前i轮中,X获得的席位不超过j的最小票数，再对X获胜情况中（X的席位>=m/2+1)取最小

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef long long ll;
ll x[N],y[N],z[N];
ll n,m=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i]>>z[i];
		m+=z[i];
	}
	vector<ll> f(m+1,1e17);
	f[0]=0;
	for(int i=0;i<=n;i++)
	{
		ll w=max((y[i]-x[i])/2+1,0ll);//每轮可以给的票数
		for(int j=m;j>=z[i];j--)
		{
			f[j]=min(f[j],f[j-z[i]]+w);
		}
	}
	ll ans=1e17;
	for(int i=m/2+1;i<=m;i++)//获胜情况
	  ans=min(ans,f[i]);//最小值
	  
	cout<<ans<<'\n';
}