# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### 选举拉票：贪心与三分的巧妙结合

posted on 2018-02-23 11:32:27 | under 平时做题+算法 |

【题目描述】选举拉票

【数据格式】

【简单样例】

$Input$#$1$：$~~~~~~~~~$ $Output$#$1$:

5                        3
1 2
1 2
1 2
2 1
0 0


$Input$#$2$：$~~~~~~~~~$ $Output$#$2$:

10                       3
0 0
3 5
4 6
3 2
4 4
2 1
2 6
0 0
2 4
3 9

### $60$~$80$分做法

int solve(int x)
{
memset(num, 0, sizeof(num));
memset(flag, 0, sizeof(flag));
for(int i=1;i<=n;i++)
num[people[i].choice]++;
int ans=0;
for(int i=1;i<=n;i++)
if(people[i].choice!=0 && num[people[i].choice]>=x)
{
ans+=people[i].price;
num[people[i].choice]--;
num[0]++;
flag[i]=true;
}
for(int i=1;i<=n;i++)
if(num[0]<x && !flag[i] && people[i].choice!=0)
{
ans+=people[i].price;
num[people[i].choice]--;
num[0]++;
flag[i]=true;
}
return ans;
}
for(int i=1;i<=n;i++)
res=min(res,solve(i));

### $100$分做法

#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 100001
using namespace std;
int n;
struct Person
{
int choice, price;
}people[MAXN];
bool cmp(const Person&A, const Person&B)
{
return A.price < B.price;
}
int num[MAXN];
bool flag[MAXN];
int solve(int x)
{
memset(num, 0, sizeof(num));
memset(flag, 0, sizeof(flag));
for(int i=1;i<=n;i++)
num[people[i].choice]++;
int ans=0;
for(int i=1;i<=n;i++)
if(people[i].choice!=0 && num[people[i].choice]>=x)
{
ans+=people[i].price;
num[people[i].choice]--;
num[0]++;
flag[i]=true;
}
for(int i=1;i<=n;i++)
if(num[0]<x && !flag[i] && people[i].choice!=0)
{
ans+=people[i].price;
num[people[i].choice]--;
num[0]++;
flag[i]=true;
}
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>people[i].choice>>people[i].price;
sort(people+1,people+1+n,cmp);
int l=1,r=n,mid1,mid2;
while(l+3<r)
{
mid1=l+(r-l)/3;
mid2=mid1+(r-l)/3;
if(solve(mid1) > solve(mid2)) l=mid1;
else r=mid2;
}
int pos=l;
for(int i=l;i<=r;i++)
if(solve(pos)>solve(i)) pos = i;
cout << solve(pos) << endl;
}