程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Delete HDU5210 (模擬貪心)

Delete HDU5210 (模擬貪心)

編輯:關於C++
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;
}

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved