题目:E. Correct Placement
题目链接:https://codeforces.com/contest/1472/problem/E
题意:有n(1 <= n <= 2e5)个人,每个人有h(高度)、w(宽度)两个值。这n个人要拍照片。对于一个人i,如果存在一个人j(j不等于i)满足wi > wj && hi > wj或 wi > hj && hi > wj,那么j就要排在i的前面。对于每个人i,求出任意的一个j。
输入:第一行输入测试用例个数t。
t 个测试用例。每个测试用例第一行是人数n。接下来n行,每行输入第i个人的高度hi和宽度wi(1 <= hi, wi <= 1e9)。
输出:对于每个i,输出任意的一个j,若不存在j,则输出 -1。
样例输入:
1
3
3 4
5 4
3 3
样例输出:
-1 3 -1
样例解释:
对于第一个人,因为h1 < h2 && h1 == h3,所以输出-1。
对于第二个人,因为h2 > w2 && w2 > h1,所以可以输出3。
对于第三个人,因为h3 = h3 && h3 < h2,所以输出-1。
题目分析:思维题。本题h和w是“等价”的,也就是说一个人的h和w是可以交换的。
解题步骤:在输入每个人的h和w的时候,如果h < w,交换。用结构体存一个人的h, w,和他是第几个人,再按w排序。遍历结构体数组,判断当前元素的h是否大于前面最小的h,若是,那么那个最小的h所对应的人就能成为当前元素的j。若当前元素的h小于前面最小的h,则要更新最小的h的值,但在更新之前要往后遍历和当前元素w相等的人,最后选择一个最小的h更新最小的h的值。
方法粗略证明:
设a1 = max(h1, w1), b1 = min(h1, w1), a2 = max(h2, w2), b2 = min(h2, w2)。
若b1 <= b2, 则有b1 <= b2, b1 <= a1, b2 <= a2,若b2 > a1,则有b1 <= a1 < b2 <= a2,也就是b2 > a1时a2也必定大于a1,所以只需要判断a2是否大于a1, 不需要判断b2是否大于a1。
AC代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
struct st{
int x, y, z;
bool operator < (const st &X) const{
return y < X.y;
}
}a[N];
int b[N];
void solve(){
int n;
scanf("%d", &n);
for(int i = 1;i <= n;i++){
scanf("%d %d", &a[i].x, &a[i].y);
if(a[i].x < a[i].y) swap(a[i].x, a[i].y);
a[i].z = i;
}
sort(a + 1, a + 1 + n);
int x = a[1].x, y = a[1].y, z = a[1].z;
b[z] = -1;
for(int i = 2;i <= n;i++){
if(a[i].x > x && a[i].y > y) b[a[i].z] = z;
else{
b[a[i].z] = -1;
if(a[i].x < x){
int k = i, j = i + 1;
for(;a[j].y == a[i].y && j <= n;j++){
if(a[j].x > x && a[j].y > y) b[a[j].z] = z;
else{
b[a[j].z] = -1;
if(a[j].x < a[k].x) k = j;
}
}
i = j - 1;
x = a[k].x, y = a[k].y, z = a[k].z;
}
}
}
for(int i = 1;i <= n;i++) printf("%d ", b[i]);
printf("\n");
}
int main(void){
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
时间复杂度:O(nlogn),因为用到了排序。
空间复杂度:O(n)。