程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Delete HDU5210 （模擬貪心）

Delete HDU5210 （模擬貪心）

編輯：C++入門知識

Delete HDU5210 （模擬貪心）

Delete
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 207 Accepted Submission(s): 140

Problem Description
WLD likes playing with numbers. One day he is playing with N integers. He wants to delete K integers from them. He likes diversity, so he wants to keep the kinds of different integers as many as possible after the deletion. But he is busy pushing, can you help him?

Input
There are Multiple Cases. (At MOST 100)

For each case:

The first line contains one integer N(0
The second line contains N integers a1,a2,...,aN(1≤ai≤N), denoting the integers WLD plays with.

The third line contains one integer K(0≤K

Output
For each case:

Print one integer. It denotes the maximum of different numbers remain after the deletion.

Sample Input

4
1 3 1 2
1

Sample Output

3

Hint
if WLD deletes a 3, the numbers remain is [1,1,2],he'll get 2 different numbers.
if WLD deletes a 2, the numbers remain is [1,1,3],he'll get 2 different numbers.
if WLD deletes a 1, the numbers remain is [1,2,3],he'll get 3 different numbers.

Source

BestCoder Round #39 ($)

1001 Delete
用一個cnt數組記下每個數在a序列中出現了幾次
在刪數的時候貪心，盡可能刪那些出現次數>1的數
這樣就可以使最後有最多不同的數


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;
templateinline T read(T&x)
{
    char c;
    while((c=getchar())<=32)if(c==EOF)return 0;
    bool ok=false;
    if(c=='-')ok=true,c=getchar();
    for(x=0; c>32; c=getchar())
        x=x*10+c-'0';
    if(ok)x=-x;
    return 1;
}
template inline T read_(T&x,T&y)
{
    return read(x)&&read(y);
}
template inline T read__(T&x,T&y,T&z)
{
    return read(x)&&read(y)&&read(z);
}
template inline void write(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
templateinline void writeln(T x)
{
    write(x);
    putchar('\n');
}
//-------ZCC IO template------
const int maxn=500;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long  LL;
typedef double DB;
typedef pair P;
#define bug printf("---\n");
#define mod  100007

int a[maxn];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,m;
    while(read(n))
    {
        memset(a,0,sizeof(a));
        int maxv=0;
        For(i,0,n)
        {
            int tmp;
            read(tmp);
            a[tmp]++;
            maxv=max(maxv,tmp);
        }
        int k;
        read(k);
        sort(a,a+101,cmp);
        int i=0;
        while(a[i])i++;

        int sum=0;
        For(j,0,i)sum+=a[j];
        sum-=i;
        k-=sum;
        if(k<=0)writeln(i);
        else writeln(i-k<0?0:i-k);

    }
    return 0;
}