E. Correct Placement(思维)

题目: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)。

上一篇:css关系选择器


下一篇:find的基本查询命令《二》