题目链接

扑克牌

时间限制: 1000 ms 内存限制: 262144 KB

【题目描述】
一副扑克牌有n张牌。一般你买的一副新扑克牌里除了这n张牌外还会有一些张特殊的牌，如果你不小心弄丢了n张牌中的某一张，就可以用特殊牌来代替，但是如果你弄丢两张的话就没有办法了，因为特殊牌上的图案是一样的。

现在你得到了很多扑克牌，准确来说，n种牌你各有a1,a2,…,an张，同时你还有b张特殊牌，现在你需要从这些牌中整理出若干副牌供大家使用。整理出的一副牌可以由n种普通牌各一张组成，也可以由n−1种普通牌各一张再加一张特殊牌组成。

请你设计出一种方案，整理出尽可能多的牌。

【输入】
第一行给出n和b。

第二行给出a1,a2,…,an。

【输出】
输出最多能整理出的牌的副数。

【输入样例】
5 5
5 5 5 5 5
【输出样例】
6
【提示】
无
【数据规模及约定】

对于20%的数据，1≤n≤100，牌的数量小于100。

对于40%的数据，1≤n≤3000。

对于100%的数据，1≤n≤1000000，牌的数量≤10^6。

思路

每副牌最多一张特殊卡
使用能用特殊卡就用特殊卡，把普通卡留给后面用

参考程序

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
#define N 1000006
using namespace std;
int n,m=N,b,ans,c;
int a[N];
int main() {
    cin>>n>>b;
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        m=min(m,a[i]);
    }
    c=min(m,b);
    ans+=m;
    while(c) {
        b-=c;
        for(int i=1; i<=n; i++)
            a[i]-=m;
        for(int i=0; c; i++)
            for(int j=1; j<=n&&c; j++)
                if(a[j]==i) {
                    c--;
                    a[j]++;
                }
        m=N;
        for(int i=1; i<=n; i++)
            m=min(m,a[i]);
        ans+=m;
        c=min(m,b);
    }
    while(b) {
        int k=0;
        for(int i=1; i<=n&&k<2; i++) {
            if(a[i]==0)
                k++;
            else
                a[i]--;
        }
        if(k==2)
            break;
        b--;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}