Avito Cool Challenge 2018 B - Farewell Party

mac2022-06-30  38

题目大意:

有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[100005]; stack <int> ans[100005]; int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) while(!ans[i].empty()) ans[i].pop(); map <int,int> mp; mp.clear(); for(int i=0;i<n;i++) { scanf("%d",&arr[i]); if(!mp.count(arr[i])) mp[arr[i]]=1; else mp[arr[i]]++; // 记录描述为q的人有多少个 } map <int,int> :: iterator it; bool OK=1; int id=1; 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==0) { // 特殊情况 for(int i=0;i<p/t;i++) { // 压入p/t种 for(int j=0;j<t;j++) // 每种t个 ans[q].push(id); id++; } } else { OK=0; break; } } else { // while(p--) ans[q].push(id); // 压入一种编号p个 id++; } } if(OK) { printf("Possible\n"); for(int i=0;i<n;i++) { printf("%d ",ans[arr[i]].top()); ans[arr[i]].pop(); } printf("\n"); } else printf("Impossible\n"); } return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/10129721.html

相关资源:JAVA上百实例源码以及开源项目
最新回复(0)