原题
还蛮有意思的一道题,先要理解题目给的输入: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;}