题意概括： 有 N 个人，每个人都佩戴一顶帽子（帽子种类有 1、2、3 … N )；
接下来 N 个数表示所有人里面 与 第 i 个人佩戴了不同帽子的总数。
解题思路: ai 代表与自己佩戴了不同帽子的个数，那么反过来意思就是说有 N - ai个人佩戴了与自己相同帽子。
如果能满足 数量为 ai 的 个数 Si == N - ai， 则说明刚好有 N-ai 个人佩戴相同帽子。
如果 Si > N-ai ,则需要判断 这 Si 个人里面能否内部平衡掉， 也就是分成若干块 N-ai，每一块佩戴不同的帽子，但是块内的人佩戴的帽子是相同的，这样也满足条件。
即 Si%（N-ai） ？= 0；
如果 Si % （N-ai） ！= 0 则说明无法平衡。
最后按块编号，输出答案。
tip：代码实现和细节很重要。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <cmath> #define INF 0x3f3f3f3f using namespace std; const int MAXN = 1e5+10; vector<vector<int> >num(MAXN); int ans[MAXN]; int main() { int N, x; scanf("%d", &N); for(int i = 1; i <= N; i++){ scanf("%d", &x); num[N-x].push_back(i); } int tp, no = 0; bool flag = true; for(int i = 1; i <= N; i++){ tp = num[i].size(); if(tp%i != 0){ flag = false; break; } for(int j = 0; j < tp; j++){ if(j%i == 0) ++no; ans[num[i][j]] = no; } } if(flag){ puts("Possible"); for(int i = 1; i <= N; i++) printf("%d ", ans[i]); } else{ puts("Impossible"); } return 0; }题意：有n顶不同的帽子，现在给你n个数，ai表示第i个人说，有ai个人与自己的帽子不同，问你是否能求出一种解决方案，能的话，输出一组。
题解：这题ai表示第i个人说，有ai个人与自己的帽子不同，那么我们可以反过来看，就是说有n-ai个人与自己的帽子相同，我们先按帽子排序一下，最后输出时再按序号排序一下。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct node { int state;///说明有state个人的帽子与我相同 int type;///存储每个人帽子的类型 int id;///存储每个人的id } num[100010]; bool cmp(node a,node b) /// { return a.state>b.state; } bool cmp1(node a,node b) { return a.id<b.id; } int book[100010];///book[i]表示记录i类型的帽子有多少个 int main() { int n; while(~scanf("%d",&n)) { memset(book,0,sizeof(book)); for(int i=1; i<=n; i++) { scanf("%d",&num[i].state); num[i].state=n-num[i].state; ///反过来 num[i].id=i; } sort(num+1,num+1+n,cmp); ///按帽子类型排 num[0].state=-1; int item=1; bool flag=true; num[1].type=1; ///初始化 int sum=num[1].state-1; for(int i=2; i<=n; i++) ///给每个人赋值帽子类型 { if(sum>0) { num[i].type=item; sum--; } else { num[i].type=++item; sum=num[i].state-1;///换下一中类型 } if(item>n) { printf("Impossible\n"); flag=false; break; } } if(flag) { bool flag2=true; for(int i=1; i<=n; i++) ///判断此分配方案是否合法 { int j=num[i].type; book[j]+=1; ///记录每种类型的数量 } for(int i=1; i<=n; i++) { if(num[i].state!=book[num[i].type]) ///如果不等，说明这方案不行了 { flag2=false; break; } } if(flag2) { sort(num+1,num+1+n,cmp1); ///按id排序一下 printf("Possible\n"); for(int i=1; i<=n; i++) printf("%d ",num[i].type); puts(""); } else { printf("Impossible\n"); } } } return 0; }