模拟题，自己写得烦死了，两个case没过，1个3分1个2分
懒得再写了
#include#include #include #include using namespace std;int np, ng;typedef struct { int id; //在ms中的下标就是其唯一识别 int weight; int lostAt; int winAt; int rank;}mouse;mouse ms[1000+5];stack loser;//每层失败的loservector order;//每次在order里找到最大的，存进winnervector winner; void findMax(int start, int end, int level){//从order[start, end)里找到最大weight的值，存进win里 int maxPos = start; int maxWeight = order[maxPos].weight; for(int j = start+1; j < end; j++){//在一个goup里找最大 if(order[j].weight > maxWeight){ maxPos = j; maxWeight = order[j].weight; } } order[maxPos].winAt = level; //test //printf("found max is%d weight is%d\n",order[maxPos].id, order[maxPos].weight ); winner.push_back(order[maxPos]);}bool cmp(const mouse a, const mouse b){ return (a.winAt>b.winAt);}int main(){ freopen("in.txt","r",stdin); scanf("%d %d",&np, &ng); //不要用order.resize(np), 会导致vector order固定大小！ for(int i = 0; i < np; i++){ mouse m; m.lostAt = 0; m.winAt = 0; m.id = i; m.rank = -1; scanf("%d", &m.weight); ms[i] = m; } for(int i = 0; i < np; i++){ int id; scanf("%d", &id); order.push_back(ms[id]); //这是个值传递，就是把ms[id]复制进order里了 } int group = np/ng; int left = np%ng; int level = 1; while(1){ //printf("leve = %d\n", level); int start, end; for(int i = 0; i < group ; i++){ start = i * ng, end = (i+1) * ng; findMax(start, end, level); } if(left > 0){//最后剩余不够ng的成一组 start = group * ng; end = order.size(); findMax(start, end, level); } for(int i = 0; i < order.size(); i++){//这一层的loser if(order[i].winAt < level){ order[i].lostAt = level; loser.push(order[i]);//loser进栈 } } int len = winner.size(); order = winner;//把winner集合作为下一轮循环的order集合 //test /*for(int i = 0; i < order.size(); i++){ if(order[i].winAt == level){ printf("%d wins at %d\n", order[i].id,order[i].winAt); } }*/ if(len == 1){ break; } group = len/ng; left = len%ng; winner.clear(); level++; } int id = winner[0].id; ms[id].rank = 1;// 第一名 int sameLevelCnt = 0; int curRank = 2; int curLevel = 2; while(!loser.empty()){ mouse m = loser.top(); id = m.id; //test //printf("id = %d winAt=%d and curLevel = %d\n",id, m.winAt, curLevel); if(m.winAt == curLevel){ //比较的是m来自loser,修改的是ms[id] sameLevelCnt++; }else if(m.winAt < curLevel){ curRank = curRank+sameLevelCnt; sameLevelCnt = 1; curLevel--; } ms[id].rank = curRank; loser.pop(); } for(int i = 0; i < np-1; i++){ printf("%d ", ms[i].rank); } printf("%d", ms[np-1].rank); return 0;}