ORIGIN

HDU-5182 PM2.5

2020-07-11

PM2.5

Nowadays we use content of PM2.5 to describe the quality of air. The lower content of PM2.5 one city have, the better quality of air it have. So we sort the cities according to the content of PM2.5 in ascending order.

Sometimes one city’s rank may raise, however the content of PM2.5 of this city may raise too. It means that the quality of this city is not promoted. So this way of sort is not rational. In order to make it reasonable, we come up with a new way to sort the cities. We order this cities through the difference between twice measurement of content of PM2.5 (first measurement – second measurement) in descending order, if there are ties, order them by the second measurement in ascending order , if also tie, order them according to the input order.

Input

Multi test cases (about 100), every case contains an integer n which represents there are n cities to be sorted in the first line.
Cities are numbered through 0 to n−1.
In the next n lines each line contains two integers which represent the first and second measurement of content of PM2.5
The ith line describes the information of city i−1
Please process to the end of file.

[Technical Specification]
all integers are in the range [1,100]

Output

For each case, output the cities’ id in one line according to their order.

Sample Input

Sample Output

1
2

0 1
0 2 1

Analysis

There are three rules to sort the structs:

First sort by the difference between the first measurement and the second measurement. (First - second), sort by decreasing order.
If it’s equal, sort by the second measurement, ascending order.
If the two condition are both equal, sort by the id. ascending order.

Code

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

struct city {
	int id, first, second, dif;
	bool operator < (const city& x) const {
		if(dif == x.dif) {
			if(second == x.second) return id < x.id;
			else return second  < x.second;
		} else return dif > x.dif;
	}
}c[10000];

int main() {
	int n;
	while(cin >> n) {
		for(int i = 0; i < n; i ++) {
			cin >> c[i].first >> c[i].second;
			c[i].dif = (c[i].first - c[i].second);
			c[i].id = i;
		}
		sort(c, c + n);
		for(int i = 0; i < n; i ++) {
			cout << c[i].id;
			if(i != n - 1) cout << " ";
			else cout << endl;
		}
	} 
}