自己的做法是 将端点离散化,枚举端点来判断是否为分割点 怎么快速判断是否为分割点呢? 用一个数组sr记录右端点,一个数组sl记录左端点,对当前长度i,二分找到i在sr和sl中的位置,相当于找到多少个线段的右端点r<=i, 多少线段的左端点 l>i 然后判断和是否为n就可以了,注意集合要求非空 这样做复杂度好像比较高
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<iostream> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<stdlib.h> #include<algorithm> #include<time.h> #include<unordered_map> #define bug1(g) cout<<"test: "<<g<<endl #define bug2(g,i) cout<<"test: "<<g<<" "<<i<<endl #define bug3(g,i,k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl #define bug4(a,g,i,k) cout<<"test: "<<a<<" "<<g<<" "<<i<<" "<<k<<endl using namespace std; typedef long long ll; const int maxn=2e5+5; int t; int n; int l[maxn],r[maxn]; set<int> a; vector<int>sl,sr; int main() { ios::sync_with_stdio(0); cin>>t; while(t--) { cin>>n; a.clear(); sl.clear(); sr.clear(); for(int i =0;i<n;i++) { cin>>l[i]>>r[i]; a.insert(l[i]); a.insert(r[i]); sl.push_back(l[i]); sr.push_back(r[i]); } sort(sl.begin(),sl.end()); sort(sr.begin(),sr.end()); int ans=-1; for(auto i=a.begin();i!=a.end();i++) { int r=upper_bound(sr.begin(),sr.end(),*i)-sr.begin(); // 一定都要用upper_bound 可以自己举例推一下 int l=sl.end()-upper_bound(sl.begin(),sl.end(),*i); if(r>0&&l>0&&r+l==n) { ans=*i; break; } } if(ans==-1) cout<<-1<<endl; else { for(int i =0;i<n;i++) { if(r[i]<=ans) cout<<1; else cout<<2; if(i==n-1) cout<<endl; else cout<<" "; } } } return 0; }看巨巨博客还有一种更简单的做法 https://blog.csdn.net/CaprYang/article/details/86419347 排序后,直接记录之前出现过的最大的r与当前的l比较就行 自己又想复杂了()
#include <stdio.h> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 2e5 + 10; struct node { int l, r, i; bool operator < (const node &oth) const { return l < oth.l; } }a[MAXN]; bool cmp(const node &a, const node &b) { return a.i < b.i; } int main() { #ifdef LOCAL freopen("C:/input.txt", "r", stdin); #endif int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].i = i; sort(a + 1, a + n + 1); //按照l排序 int k = 0, r = a[1].r; //最远的r for (int i = 2; i <= n; i++) { if (a[i].l > r) //当前位置没覆盖到之前的r k = a[i].l; //记录可行的l r = max(r, a[i].r); } sort(a + 1, a + n + 1, cmp); if (k) for (int i = 1; i <= n; i++) //大于等于k所记录的分为第二组 cout << (a[i].l >= k ? 2 : 1) << " "; else cout << -1; cout << endl; } return 0; }