Farewell Party-构造

Farewell Party

思路 ： 转换思路 ，有 a [ i ] 个不相等的 ，那么至少得有 n – a [ i ]个与它相等的。 但是有可能与它拥有相同数目的有很多。

但是为了能够最终 分配成成功  总的 个数 % N – a [ i ] 必须 == 0。所以 这样判断完否定之后 进行分配时需要操作的就是，

把 每 N – a [ i ]  个 a [ i ]  设置为同一颜色即可 。

#include<bits/stdc++.h>
using namespace std;
#define maxn 123456
int a[maxn],n,tong[maxn],ss[maxn];
int vis[maxn],id=0,flag,ans[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        tong[a[i]]++;
    }
    for(int i=1; i<=n; i++)
    {
        if(tong[a[i]]<n-a[i])flag=1;
        if(tong[a[i]]%(n-a[i])!=0)flag=1;
        if(vis[a[i]]!=0&&ss[a[i]]<n-a[i])
        {
            ans[i]=vis[a[i]];
            ss[a[i]]++;
        }
        else if(vis[a[i]]!=0&&ss[a[i]]==n-a[i])
        {
            ans[i]=vis[a[i]]=++id;
            ss[a[i]]=1;
        }
        else
        {
            ans[i]=vis[a[i]]=++id;
            ss[a[i]]++;
        }
    }
    if(flag)printf("Impossible\n");
    else
    {
        printf("Possible\n");
        for(int i=1; i<=n; i++)
        {
            printf("%d",ans[i]);
            if(i==n)printf("\n");
            else printf(" ");
        }
    }
    return 0;
}