生活随笔
收集整理的這篇文章主要介紹了
Codeforces Round #693 (Div. 3) E. Correct Placement 思维
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
傳送門(mén)
題意：
思路： 對(duì)于每個(gè)人都有個(gè)二元組(x,y)(x,y)(x,y)，從題意中提取有效信息就是：當(dāng)(x1,y1)(x_1,y_1)(x1?,y1?)的最大值大于(x2,y2)(x_2,y_2)(x2?,y2?)的最大值，(x1,y1)(x_1,y_1)(x1?,y1?)的最小值大于(x2,y2)(x_2,y_2)(x2?,y2?)的最小值，那么(x2,y2)(x_2,y_2)(x2?,y2?)就是符合條件的。這樣我們可以對(duì)于hhh和www，如果h<wh<wh<w,那么就交換hhh和www。讓后按照hhh排序，從頭維護(hù)一個(gè)www的最小值和對(duì)應(yīng)的ididid，讓后在hhh不相等的時(shí)候更新就好啦。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int ans
[N
];
struct Node
{int x
,y
;int id
;bool operator < (const Node
&W
) const{if(x
!=W
.x
) return x
<W
.x
;else return y
<W
.y
;}
}q
[N
];int main()
{
int _
; scanf("%d",&_
);while(_
--){scanf("%d",&n
);for(int i
=1;i
<=n
;i
++){ans
[i
]=-1;scanf("%d%d",&q
[i
].x
,&q
[i
].y
); q
[i
].id
=i
;if(q
[i
].x
<q
[i
].y
) swap(q
[i
].x
,q
[i
].y
);}sort(q
+1,q
+1+n
);int mi
=INF
,id
=-1;for(int i
=1;i
<=n
;i
++){int x
=q
[i
].x
,now
=i
;while(i
<=n
&&x
==q
[i
].x
){if(mi
!=INF
&&mi
<q
[i
].y
) ans
[q
[i
].id
]=id
;i
++;}i
--;if(mi
>q
[now
].y
) mi
=q
[now
].y
,id
=q
[now
].id
;}for(int i
=1;i
<=n
;i
++) printf("%d ",ans
[i
]);puts("");}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #693 (Div. 3) E. Correct Placement 思维的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
