hdu_round1-1002 光头强选举(优先队列)_光头强选举 csdn-CSDN博客

本文链接：https://blog.csdn.net/oranges_c/article/details/74158947

本文介绍了一道关于光头强通过贿赂手段赢得选举的算法题。通过使用优先队列维护最大票数的方法，实现光头强以最少的贿赂次数获胜。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

记录一个菜逼的成长。。

因为这要账号才能看到题目，所以这里把题目复制出来了..

光头强选举

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 156 Accepted Submission(s): 73

Problem Description
光头强非常渴望权利。他想赢得即将到来的选举。
现在有n个候选人，包括光头强，其中光头强是一号候选人。我们现在已经知道每个候选人获得了多少张选票。其中第i个候选人拥有ai张选票。为了赢得选举，光头强的得票数必须严格大于其他候选人。
胜利比一切都重要，所以光头强决定通过作弊来赢得选举。他会通过贿赂将给其竞争者投票的选民将选票改投给自己。那么光头强最少要贿赂几个选民才能获得选举的胜利？

Input
输入数据包含多个测试实例，每个测试实例的第一行有整数 n (2≤ n ≤ 100)，表示有n个候选人。
接下来1行有n个数 a1 , a2 ,… an (1 ≤ai≤ 1000)表示每个候选人的票数。

Output
对于每个测试实例，输出最少要贿赂几个人才能使光头强赢得选举（他的得票数严格大于其他所有候选人）

Sample Input
4
1 8 8 8
5
5 1 11 2 8

Sample Output
6
4
Hint

第一个样例：从其他三个候选人手里各拿到两张选票，最终结果为 7 6 6 6，其中光头强为1号，所以胜利。

看到这题就知道是cf上翻译过来的一道题。
只要每次选取最大的数减1，加到自身上就行了。
用优先队列维护最大值

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
  int n;
  while(~scanf("%d",&n)){
    int ans = 0;
    priority_queue<int>pq;
    int s;scanf("%d",&s);
    for( int i = 1; i < n; i++ ){
      int x;
      scanf("%d",&x);
      pq.push(x);
    }
    while(s <= pq.top()){
      int t = pq.top();pq.pop();
      t--;
      ans++,s++;
      pq.push(t);
    }
    printf("%d\n",ans);
  }
  return 0;
}