题目链接：http://codeforces.com/problemset/problem/471/B
题目意思：有 n 个 tasks，编号依次为 1 ～ n，每个 task 都有一定的难度值来评估。例如，第 i 个 task 的难度值为 hi。现在的任务是把 n 个 task 全部完成，难度值越小的task越先完成。有3个人，都希望自己完成所有task的输出序列是与众不同的，问是否存在至少3条完成所有task的不同序列，没有的话输出 “NO”，否则输出“YES”并输出3条不同的完成序列。
昨晚比赛的题目，有一点点思路，但最终调不出来，泪～～。
小小的思路： 首先要知道有解的情况是什么。当时想到的是：两种情况。（1）相同难度值（difficulty）的task 至少有3个，类似这种序列：1 2 3 3 3 5 （2）相同 difficulty 的 task 有2个，但这种类型的task 至少有2个，类似这种序列： 1 2 2 4 4 5
不过处理起来确实复杂无比，甚至用到 vector 来存储每个难度值的邻接表，总的来说就是想得太复杂啦！！
看了下别人的代码，发现思路其实是没有错的，还算是有一点点欣慰 ^_^
首先判断是否能找到3条不同序列。用一个 used 数组来统计difficulty相同的task有多少个。处理的时候同常规办法有一点点不同，是先 used[h[i]] 再 count，但 used[h[i]]++在这条语句之后，这样处理的巧妙之处就是把我上面的两种情况都包括上去了，不用另外讨论。
另外，可以用pair<int, int> 来解决存储问题，first值保存task的difficulty，second值保存task的id。排序是很容易想到的，因为要按题目要求，难度值越少的task越先做嘛～～
最后一个问题就是，如何得到3条不同的序列，用 swap 可以解决。由于排序之后，对于相同difficulty的task，它们的 id 默认是从小到大排序的，那么swap 的条件是，对于相同difficulty 的task，交换那些 后面 id > 前面 id 的task。可以知道，每交换一次，就得到一条新的完成序列。
版本1（个人比较喜欢这个多点）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; #define f first
#define s second
typedef pair<int, int> pii; const int maxn = + ;
pii task[maxn];
int used[maxn]; int main()
{
int n;
// freopen("input.txt", "r", stdin);
while (scanf("%d", &n) != EOF)
{
int in, count = ;
memset(used, , sizeof(used));
for (int i = ; i <= n; i++)
{
scanf("%d", &in);
task[i] = pii(in, i); // 巧妙的赋值
if (used[in])
count++;
used[in]++;
}
if (count < )
printf("NO\n");
else
{
printf("YES\n");
sort(task+, task++n); // 默认按pair first 排序 for (int time = ; time < ; time++)
{
for (int i = ; i <= n; i++)
printf("%d ", task[i].s);
printf("\n"); for (int i = ; i < n; i++)
{
if (task[i].f == task[i+].f && task[i].s < task[i+].s)
{
swap(task[i], task[i+]);
break;
}
}
}
}
}
return ;
}
版本2（比赛时死也调不出来，看了别人的在原来基础上改的）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
struct node{
int id;
int h;
}task[maxn]; int cmp(node a, node b)
{
return a.h < b.h;
} int cnt[maxn]; int main()
{
int n;
// freopen("input.txt", "r", stdin);
while (scanf("%d", &n) != EOF)
{
int t, c0 = ;
bool flag = false;
memset(cnt, , sizeof(cnt));
for (int i = ; i <= n; i++)
{
scanf("%d", &t);
task[i].h = t;
task[i].id = i; if (cnt[t]) // 同一个h值出现3次以上/两个以上的h值出现2次以上
c0++;
cnt[t]++;
}
if (c0 < )
printf("NO\n");
else
{
printf("YES\n");
sort(task+, task++n, cmp);
for (int time = ; time < ; time++)
{
for (int i = ; i <= n; i++)
printf("%d ", task[i].id);
printf("\n"); for (int i = ; i < n; i++)
{
if (task[i].h == task[i+].h && task[i].id < task[i+].id)
{
swap(task[i], task[i+]);
break;
}
}
}
}
}
return ;
}