CodeForces 353 B.Two Heaps (greed)

Description

Given 2n two digit numbers, now we need to divide them into two sets. Each set has n numbers. After the set is divided, we can take one number from two sets to form a four digit number. If the number is divided, we can get the most kinds of numbers

Input

The first line is an integer n, and then input 2n two digit ai(1 ≤ n ≤ 100)

Output

First, input the maximum number of digital categories that can be composed, and then output 2n 1 or 2 to represent the set of which this number belongs

Sample Input

1

10 99

Sample Output

1

2 1

Solution

For the number of more than 1, give each set one first, for the number of 1, try to divide it into two sets equally, and give the rest randomly

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=205;
int n,a[maxn],ans[maxn],num[maxn],vis[maxn];
int main()
{
    while(~scanf("%d",&n))
    {
        memset(num,0,sizeof(num));
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=2*n;i++)
        {
            scanf("%d",&a[i]);
            num[a[i]]++;
        }
        int num0=0,num1=0,num2=0;
        for(int i=1;i<=2*n;i++)
        {
            if(num[a[i]]>=2)
            {
                if(!vis[a[i]])num0++,ans[i]=1,vis[a[i]]=1;
                else if(vis[a[i]]==1)ans[i]=2,vis[a[i]]=2;
            }
            else
            {
                if(num1>num2)ans[i]=2,num2++;
                else ans[i]=1,num1++;
            }
        }
        num1+=num0,num2+=num0;
        printf("%d\n",num1*num2);
        for(int i=1;i<=2*n;i++)
            if(vis[a[i]]==2&&!ans[i])
            {
                if(num1<n)ans[i]=1,num1++;
                else ans[i]=2;
            }
        for(int i=1;i<=2*n;i++)printf("%d%c",ans[i],i==2*n?'\n':' ');
    }
    return 0;
}

Tags: REST

Posted on Tue, 05 May 2020 10:57:48 -0700 by larrygingras