CodeforcesRound#503(bySIS,Div.2)C.Elections

#include
#include
#include
#include
using namespace std;
struct sss
{int id;int cost;
}a[3001];
int f[3001];
int g[3001];
int cmp(struct sss x,struct sss y)
{return x.cost<y.cost;
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d%d",&a[i].id,&a[i].cost);f[a[i].id]&＃43;&＃43;;//计入最开始的投票情况
}long long sum&＃61;999999999999,sum2&＃61;0,ans;sort(a&＃43;1,a&＃43;n&＃43;1,cmp);//按价格排好序for(int i&＃61;f[1];i<&＃61;n;i&＃43;&＃43;)//枚举获胜状态
{sum2&＃61;0;ans&＃61;0;for(int j&＃61;2;j<&＃61;m;j&＃43;&＃43;){if(f[j]>&＃61;i){g[j]&＃61;f[j]-i&＃43;1;//记录要赢得此选手要在他这买几票sum2&＃43;&＃61;g[j];//记录总共要在比他高的选手这买几票
}else g[j]&＃61;0;}if(i-f[1]continue;//如果我在比他高的选手这买的票比我总共买的还多说明情况不存在sum2&＃61;i-f[1]-sum2;//记录要在比我低的选手这买几票for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){if(g[a[j].id]!&＃61;0)//比我高
{g[a[j].id]--;ans&＃43;&＃61;a[j].cost;}else{if(sum2!&＃61;0&&a[j].id!&＃61;1)//比我低&＃xff0c;并且我还需要买票
{sum2--;ans&＃43;&＃61;a[j].cost;}}}sum&＃61;min(sum,ans);//取最优
}cout<<sum;
}