Avito Cool Challenge 2018 B

题目大意：

有n个人

接下来一行n个数a[i] 表示第i个人描述其他人有a[i]个的帽子跟他不一样

帽子编号为1~n 如果所有的描述都是正确的

输出possible 再输出一行b[i] 表示第i个人的帽子的编号

如果存在矛盾输出impossible

如果存在p 个人都描述有q个人跟他们的帽子不一样

此时若 p+q=n 说明正确且这p个人的帽子都一样

如

a[] = 3 3 2 2 2 ，此时一种解为 b[] = 1 1 2 2 2

存在p=2个人描述有q=3个人跟他们不一样说明这两个人的帽子编号是一样的

但是这种方法存在一种特殊情况

如

a[] = 4 4 4 4 4 4 ，如果按上面的解法此时则无解

但是实际上存在一种解即 b[] = 1 1 2 2 3 3

不过可以看出来这种特殊情况每种帽子对应的人数是一样多的

那么此时存在p=6个人描述有q=4个人跟他们不一样

可以得到每种帽子对应人数为 t

判断一下p能不能整除t 若能说明描述正确

否则描述矛盾 impossible

题目要求对应第i个人输出帽子编号。。英语渣给跪了错在这里以为不需要对应

不需要对应很好处理需要对应其实也不难

开了一排栈~

第一种情况在ans[q]压入一种编号p个

特殊情况在ans[q]压入p/t种编号t个

最后从每个人的描述arr[i]里取ans[arr[i]]的栈顶输出就行了

#include <bits/stdc++.h>

#define LL long long

#define INF 0x3f3f3f3f

using namespace std;

int n, arr[];

stack <int> ans[];

int main()

{

    while(~scanf("%d",&n)) {

        for(int i=;i<=n;i++)

            while(!ans[i].empty())

                ans[i].pop();

        map <int,int> mp; mp.clear();

        for(int i=;i<n;i++) {

            scanf("%d",&arr[i]);

            if(!mp.count(arr[i])) mp[arr[i]]=;

            else mp[arr[i]]++; // 记录描述为q的人有多少个

        }

        map <int,int> :: iterator it;

        bool OK=; int id=;

        for(it=mp.begin();it!=mp.end();it++) {

            int q=(*it).first, p=(*it).second;

            if(p+q!=n) {

                int t=n-q;

                if(p%t==) { // 特殊情况

                    for(int i=;i<p/t;i++) { // 压入p/t种

                        for(int j=;j<t;j++) // 每种t个

                            ans[q].push(id);

                        id++;

                    }

                } else {

                    OK=; break;

                }

            }

            else { //

                while(p--) ans[q].push(id); // 压入一种编号p个

                id++;

            }

        }

        if(OK) {

            printf("Possible\n");

            for(int i=;i<n;i++) {

                printf("%d ",ans[arr[i]].top());

                ans[arr[i]].pop();

            } printf("\n");

        } else printf("Impossible\n");

    }

    return ;

}

巴特西

Avito Cool Challenge 2018 B - Farewell Party

最新文章

热门文章