3. 竞选总统
题目ID：20019必做题100分
最新提交：
Wrong Answer
10 分
历史最高：
Wrong Answer
40 分
时间限制: 2000ms
空间限制: 262144kB
题目描述
小信和小友正在竞选。
有 NN 个选区。ii个选区有Xi+YiXi+Yi个选民，其中XiXi个是小信的，YiYi个是小友的。Xi+YiXi+Yi总是奇数）。
在每个选区，多数党赢得该选区的所有ZiZi个席位。然后，谁赢得了整个NN区的多数席位，谁就赢得了选举。∑i=1NZii=1∑NZi为奇数）。
至少要有多少选民从小友转向小信，小信才能赢得选举？输入格式
第一行一个整数 nn，表示有 nn 个选区。
接下来 nn 行，每行三个数字 xi,yi,zixi,yi,zi，分别是小信的选民和小友的选民，以及席位数。
输出格式
输出一个整数。
样例
Input 1
1 3 8 1
Output 1
3
Input 2
2 3 6 2 1 8 5
Output 2
4
Input 3
3 3 4 2 1 2 3 7 2 6
Output 3
0
Input 4
10 1878 2089 16 1982 1769 13 2148 1601 14 2189 2362 15 2268 2279 16 2394 2841 18 2926 2971 20 3091 2146 20 3878 4685 38 4504 4617 29
Output 4
86
数据范围
- 1≤N≤1001≤N≤100
- 0≤Xi,Yi≤1090≤Xi,Yi≤109
- Xi+YiXi+Yi 是奇数
- 1≤Zi1≤Zi
- ∑i=1NZi≤105i=1∑NZi≤105
- ∑i=1NZii=1∑NZi 是奇数。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int w[105];
int z[105];
long long sum;
int dp[100005];
int ans=INT_MAX;;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d%d",&x,&y,&z[i]);
w[i]=max(0,(y-x+1)/2);
sum+=z[i];
}
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=z[i];j<=n;j++){
dp[j]=min(dp[j-z[i]]+w[i],dp[j]);
}
}
for(int i=(sum+1)/2;i<=sum;i++){
ans=min(dp[i],ans);
}
cout<<ans;
return 0;
}
/*
颠倒空格
*/
这道题输出0能拿40分但是我想要正解啊啊啊啊啊啊啊啊啊啊啊啊QAQ