https://codeforces.com/contest/1472/problem/E
題意：有好多個矩形，已知它們的長a和寬b和出現順序，對于每個矩形A，尋找任意一個矩形B，使得A能放在B上且不蓋住B（即Aa<Ba&&Ab<Bb||Aa<Bb&&Ab<Ba）,找不到就輸出-1，
首先要注意時找到任意一個矩形即可，我們先定義a為較大值，b為較小值，這樣就只需要判斷Aa<Ba&&Ab<Bb，然后我們以a為升序排列陣列，這樣就能保證對于每個矩形i，i-1的a<=i的a，
之后就是關鍵，上述的操作使我們不用考慮a的大小，所以只需要不斷更新一個min為出現過的i中最小的b，來判斷i的b是否大于min，滿足就選擇min所指的i，不滿足就輸出-1，然后更新min為i的b，
但是這樣會帶來個問題，例如 1 3 ，2 3， 2 4 ，2 5，我們會在i=2時更新min為3，這樣會使i=3，i=4的時候找不到答案，輸出-1，
怎么解決嘞？我們讓a相同的時候b為降序排序就行，這樣就是1 3,2 5，2 4,2 3，此時就不會產生上述問題辣，
（這里要注意我們對陣列排序后元素的原來出現順序就被打亂了，所以在更新了每個元素對應的答案之后要重新排序回來）
#include <bits/stdc++.h>
using namespace std;
#define qc std::ios::sync_with_stdio(0);
struct bag {
long long a;
long long b;
int num;
int ans;
};
struct bag a[200001];
bool cmp(bag a, bag b) {
if (a.a == b.a)
return a.b > b.b; //防止1 3, 2 3, 2 4，第三個元素找不到答案的情況
else
return a.a < b.a;
}
bool cmp2(bag a, bag b) {
return a.num < b.num;
}
int main() {
qc;
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].a >> a[i].b ;
//定義a為較大值，b為較小值
long long maxa = max(a[i].a, a[i].b);
long long minb = min(a[i].a, a[i].b);
a[i].a = maxa;
a[i].b = minb;
//初始化每個元素的答案為-1
a[i].ans = -1;
//給元素按順序編號
a[i].num = i + 1;
}
sort(a, a + n, cmp);//a升序排列
int miner = 0;
for (int i = 1; i < n; i++) {
if (a[i].b > a[miner].b) {
a[i].ans = a[miner].num;
}
if (a[i].b < a[miner].b) {
miner = i; //更新miner
}
}
sort(a, a + n, cmp2); //恢復原來的排列
for (int i = 0; i < n; i++) {
cout << a[i].ans << " ";
}
cout << endl;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/245707.html
標籤：其他
上一篇：qq-jsp登錄