[PAT解题报告] Mice and Rice
简单题，有趣的背景：题目给定了n个程序员用程序制作了n个老鼠，每人制作一个，所有的老鼠重量都不同，把它们每m个分为一组，不足m个话，余数也分为一组，然后每组最重的老鼠获胜进入下一轮，失败的老鼠名次是相同的，老鼠对应程序员……
问最后每个人的名次。
主要问题在于： 下一轮有多少组？ 如果现在剩余remain只老鼠，下一轮应该剩余 next = (remain + m - 1)
/ m只 ，其实是需要上取整，对于正整数，我们加上m - 1， 再除以m（下）取整就等于上取整了。那本轮淘汰的那些的名次都应该是(next
+ 1),因为这next个人占据next这么多个位置……
所以我们不断循环直到remain等于为止就好了。
注意老鼠和程序员的对应关系，还有不足m个的组也要单独看作一个组……
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int a[1024],b[1024], r[1024];
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0; i < n; ++i) {
scanf("%d", a + i);
}
for (int i = 0; i < n; ++i) {
scanf("%d",b + i);
}
for (int remain = n;remain > 1; ) {
int next = (remain + m - 1) / m, num = 0;
for (int i = 0; i < remain; i += m) {
int p = -1;
for (int j = 0; (j < m) && (i + j < remain); ++j) {
p = max(p, a[b[i + j]]);
}
for (int j = 0; (j < m) && (i + j < remain); ++j) {
if (p == a[b[i + j]]) {
b[num++] = b[i + j];
}
else {
r[b[i + j]] = next + 1;
}
}
}
remain = next;
}
r[b[0]] = 1;
for (int i = 0; i < n; ++i) {
if (i) {
putchar(' ');
}
printf("%d",r[i]);
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1056