HDOJ6188 Duizi and Shunzi (greedy)

Title Link
Idea: first of all, we can think that the answer of matching pairs must be big. Then, if matching to i, the matching pair will have one card left. See if i+1 is an odd number of cards. If so, match i, i+1, i+2 directly. Even if i+2 is an even number of cards, it is just to change the surplus for a pair. But the remaining card of i+2 may match the next card as a surplus. Case This is illustrated by 4.

/*First of all, make a pair first. It's a good deal.
But if the current number is the last of three consecutive numbers
 So, if you put 3 together, for example, 123345, after you put 3 together, you may also put 3 together with the back
 If you get it right, there's no chance for you to follow suit*/

#include<iostream>
#include<cstring>
#define maxn 1000000
using namespace std;
int a[maxn];
int main(){
    int n,m,x;
    while(cin>>n){
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++){
            cin>>x;
            a[x]++;
        }
        int ans=0;
        for(int i=1;i<=maxn;i++){
            if(a[i]>=2){
                ans+=a[i]/2;
                a[i]=a[i]%2;
            }
            //The current a[i] is either 1 or 0 
            if(a[i]<=maxn-2){
                if(a[i]==1 &&a[i+1]%2!=0 &&a[i+2]){
                    ans++;
                    a[i]--;a[i+1]--;a[i+2]--; 
                }
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}

Here is the code of WA

#include<cstring>
#define maxn 100010
using namespace std;
typedef long long ll;
ll n,x,ans;
ll a[maxn];
int main(){
    while(cin>>n){
        memset(a,0,sizeof(a));
        ans=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&x);
            a[x]++;
        }
        /*First of all, make a pair first. It's a good deal.
        But if the current number is the last of three consecutive numbers
        Then make up Shun Zi, for example, 123345. After you make up Shun Zi 123 with 3, 3 may also make up Shun Zi with the back
        If you get it right, there's no chance for you to follow suit*/
        for(int i=1;i<=maxn;i++){
            //Get along with each other 
            if(a[i]>=2){
                ans+=a[i]/2;
                a[i]=a[i]%2;
            }
            //Get along with others 
            if(i<=maxn-2){
                if(a[i+2] &&a[i]==1 &&a[i+1]%2!=0){
                    ans++;
                    a[i]--;a[i+1]--;a[i+2]--;
                }
            }
        }
        cout<<ans<<endl;
    }   
    return 0;
}

Posted on Wed, 01 Apr 2020 10:26:31 -0700 by monarlte