admin 管理员组

文章数量: 1087649

小米OJ #18 帮小学生排队

原题

还蛮有意思的一道题，先要理解题目给的输入：h和k是一对一对给的，因此对每位小朋友位置进行变动的时候，h，k应是一起变动。（一开始理解成了h,k混着给，想了半天没想出思路）
用两个数组同步保存h,k，再利用第三个数组保存h,k的索引。
首先进行一次排序：h值大的在前；h值相同的，则k值更小的在前。
随后可以发现，每对hk的正确位置应该是插入到 距离其当前位置向前(pos-k)个长度的位置。
利用个数字保存正确位置。

#include <bits/stdc++.h>
using namespace std;
int h[1001];
int k[1001];
int ind[1001];
int res[1001];bool cmp(int i, int j)
{if (h[i] == h[j])return k[i] < k[j];elsereturn h[i] > h[j];
}
int main()
{int n = 0;while (cin >> n){memset(res, -1, sizeof(res));for (int i = 0; i < n; i++){cin >> h[i] >> k[i];ind[i] = i;}sort(ind, ind + n, cmp);for (int i = 0; i < n; i++){int cur = k[ind[i]];for (int j = i; j > cur; j--){res[j] = res[j - 1];}res[cur] = ind[i];}for (int i = 0; i < n; i++){cout << h[res[i]] << " " << k[res[i]] << " ";}cout << endl;}return 0;
}

本文标签： 小米OJ 18 帮小学生排队

版权声明：本文标题：小米OJ #18 帮小学生排队 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700324133a397078.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。