题解 | #花音的礼物分配#
Smile! 花音的礼物分配（smile）
https://ac.nowcoder.com/acm/contest/90635/C
我们只需要枚举所有花音能分到的礼物就行了
using namespace std;
int n,a[510],sum1,cnt,s,dp[250010],ans=0x7fffffff;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) {
int x,op;
cin>>x>>op;
s+=x;
if(!(op-1)) sum1+=x;
if(!op) a[++cnt]=x;
}
dp[sum1]=1;
for(int i=1;i<=cnt;i++){
for(int j=s-a[i];j>=sum1;j--){
if(dp[j])
dp[j+a[i]]=1;
}
}
for(int i=sum1;i<=s;i++)
if(dp[i]) ans=min(ans,abs(s-i*2));
cout<<ans;
return 0;
}
滴滴公司福利 1815人发布