枚举每个获胜的可能的票数 + 按照花费排序
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- #define ll long long
- using namespace std;
- struct node
- {
- int id,cost;
- } a[3004];
- bool cmp(node a,node b)
- {
- return a.cost<b.cost;
- }
- int g[3004];
- int f[3004];
- int main()
- {
- int n,m;
- while(~scanf("%d%d",&n,&m))
- {
- ll sum=999999999999;
- ll sum2=0;
- ll ans;
- memset(f,0,sizeof(f));
- memset(g,0,sizeof(g));
- for (int i=1; i<=n; i++)
- {
- scanf("%d%d",&a[i].id,&a[i].cost);
- f[a[i].id]++;
- }
- sort(a+1,a+1+n,cmp);
- for (int i=f[1]; i<=n; i++) // 枚举赢需要多少票数
- {
- sum2=0;
- ans=0;
- for (int j=2; j<=m; j++)
- {
- if (f[j]>=i)
- {
- g[j]=(f[j]-i+1);// 必须降到比我少一票
- sum2+=g[j];
- }
- else
- {
- g[j]=0;
- }
- }
- if (i-f[1]<sum2)continue;// 如果我最终的票数无法赢别人这个状态就是不满足的
- sum2=i-f[1]-sum2;// 需要从票数比我低的人的那里买多少
- for (int j=1; j<=n; j++)
- {
- if (g[a[j].id]!=0)
- {
- g[a[j].id]--;// 比我高的票数减一
- ans+=a[j].cost;
- }
- else
- {
- if (sum2!=0 && a[j].id!=1)// 如果我需要在比我的低的人那里买多少
- {
- sum2--;
- ans+=a[j].cost;
- }
- }
- }
- sum=min(sum,ans);
- }
- cout<<sum<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2726918.html