poker

一副扑克牌有n张牌。一般你买的一副新扑克牌里除了这n张牌外还会有一些张特殊的牌，如
果你不小心弄丢了n张牌中的某一张，就可以用特殊牌来代替，但是如果你弄丢两张的话就
没有办法了，因为特殊牌上的图案是一样的。
现在你得到了很多扑克牌，准确来说，n种牌你各有a1、a2、……、an张，同时你还有b张特
殊牌，现在你需要从这些牌中整理出若干副牌供大家使用。整理出的一副牌可以由n种普通
牌各一张组成，也可以由n-1种普通牌各一张再加一张特殊牌组成。
请你设计出一种方案，整理出尽可能多的牌。
Input
输入包括2行
第一行给出n和b1
第二行给出a1,a2…an。
1<=n<=1000000牌的数量<=10^6
Output
输出最多能整理出的牌的副数。
Sample Input
5 5
5 5 5 5 5
Sample Output
6

大概思路:模拟一下这个样例
5 4
1 2 3 4 5
我们就能知道，应该尽量将特殊牌分给数量最少的那种牌。
比如上面这个样例
第一轮:用一张特殊牌代替1,然后第2到第五种牌各出一张
第二轮:用一张特殊牌代替1,然后第2到第五种牌各出一张
第三轮:用一张特殊牌代替2,然后第1,第3,第4，第6种牌各出一张
game over!

程序实现环节
发现整个过程，我们需要不断去找最小值，于是想到了heap
进而发现我们如果每次使用一张特殊牌代表某种牌，其它牌各出一张即相当于它们的数字都要减少一个1。这个操作起来是有点麻烦的，要将N-1个数字统统减1，复杂度是N平方的。于是我们设一个变量ans,到目前为止每种牌要减去多少个。
于是对于
1 2 3 4 5
第1轮，最小值为1,给它加上1，得到新数列2 2 3 4 5,ans=1
第2轮，最小值为2,给它加上1，得到新数列2 3 3 4 5,ans=2
第3轮，最小值为2,给它加上1，得到新数列3 3 3 4 5,ans=3
注意此时数列中最小的两个数字均为3,ans也等于3
说明最小的两个数字3,其实真实的值应该是为0的。
于是游戏结束，因为游戏如果再要继续下去的话，则要派出两张特殊牌分别给这两种牌，与题意不合。
最后注意输出结果应该为堆顶元素的值，而不是ans。
这样随便跑一个样例就知道，比如
5 1
5 5 5 5 5
最终结果应该是5,而不是1

#include<queue>

#include<cstdio>

#include<cstring>

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

int a[maxn],ans=0;

priority_queue<int,vector<int>,greater<int> >q;

int read(){

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int main(){

int n=read(),b=read();

for(int i=1;i<=n;i++)a[i]=read(),q.push(a[i]);

for(int i=1;i<=b;i++)

{

ans++;

int x=q.top();//出现次数最小的

q.pop();

x++;

q.push(x); //相当于它加了1

int x1=q.top();

q.pop();

int x2=q.top();

q.pop();

q.push(x1);//记得丢回去

q.push(x2);

if(ans==x2&&ans==x1)

    break;

}

printf("%d\n",q.top());

return 0;

}

巴特西

poker

最新文章

热门文章