四川平台网站建设方案,建设银行流水网站,长沙优化网站分析,chrome谷歌浏览器官方下载传送门
题意#xff1a;NNN个人给MMM个党派投票#xff0c;开始时每个人选择一个党派投票#xff08;给定#xff09;#xff0c;每个人可以花费一定代价贿赂#xff08;每个人给定代价#xff09;#xff0c;求让1号党派胜出#xff08;票数严格最大#xff09;的最…传送门
题意NNN个人给MMM个党派投票开始时每个人选择一个党派投票给定每个人可以花费一定代价贿赂每个人给定代价求让1号党派胜出票数严格最大的最小花费。
1≤N,M≤30001\leq N,M\leq 30001≤N,M≤3000
枚举1号党派的最终票数胜出的条件下kkk。
首先其他党派的票数必须小于kkk所以把它的最便宜的人挖掉直到小于kkk。
如果此时的票数仍然小于kkk再在剩下的人中选出最小的。
复杂度O(NM)O(NM)O(NM)
鬼知道怎么想到的
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#include algorithm
#define MAXN 3005
using namespace std;
typedef long long ll;
vectorint v[MAXN];
int lis[MAXN];
int main()
{int n,m;scanf(%d%d,n,m);for (int i1;in;i){int p,c;scanf(%d%d,p,c);v[p].push_back(c);}for (int i1;im;i) sort(v[i].begin(),v[i].end());ll ans1e18;for (int k1;kn;k){int nowv[1].size();ll sum0;lis[0]0;for (int i2;im;i){for (int j0;j(int)v[i].size()-k1;j){sumv[i][j];now;}for (int jmax(0,(int)v[i].size()-k1);jv[i].size();j)lis[lis[0]]v[i][j];}sort(lis1,lislis[0]1);for (int i1;ik-now;i) sumlis[i];ansmin(ans,sum);}coutans;return 0;
}
