与众不同的思路

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int INF = 0x3f;
struct cow{
	public:
		int l, r, id;
	public:
		void read(int i){
			cin >> l >> r;
			id = i;
		}
	private:
		void debug(){
			printf("l = %d,r = %d,id = %d\n", l, r, id);
		}
}cows[MAXN];
int ans[MAXN];
int n;
struct greater_q{
	bool operator()(cow a, cow b){
		return a.r > b.r;
	}
}; 
priority_queue<cow, vector<cow>, greater_q> q;
bool cmp(cow a,cow b){
	if(a.l == b.l)return a.r < b.r;
	return a.l < b.l;
}
int main()
{
	cin >> n;
	for(int i = 1;i <= n; i++){
		cows[i].read(i);
	}
	sort(cows + 1,cows + 1 + n, cmp);
	int cnt = 0;
	for(int i = 1;i <= n; i++){
		if(q.empty() || q.top().r >= cows[i].l){//开启新畜栏
			cnt++;
			ans[cows[i].id] = cnt;
			q.push(cows[i]);
		}
		else{//使用旧畜栏
			ans[cows[i].id] = ans[q.top().id];
			q.pop();
			q.push(cows[i]);
		}
	}
	cout << cnt << endl;
	for(int i = 1;i <= n; i++){
		cout << ans[i] << endl;
	}
    return 0;
}

~包过~111

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
 
int n;
typedef pair<int,int> PII; 
pair<PII,int> cows[50010];//记录每头牛吃草的时间段，奶牛编号
int id[50010];//记录每头牛的栅栏号; 
 
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>cows[i].first.first>>cows[i].first.second;
		cows[i].second=i;
	} 
	sort(cows,cows+n);	priority_queue<PII,vector<PII>,greater<PII> > qu;
	for(int i=0;i<n;i++){
		if(qu.empty()||cows[i].first.first<=qu.top().first){
			id[cows[i].second]=qu.size()+1;
			PII a1;
			a1.first=cows[i].first.second;
			a1.second=qu.size()+1;
			qu.push(a1);
		}
		else{
			PII a=qu.top();
			qu.pop();
			PII b;
			b.first=cows[i].first.second;
			b.second=a.second;
			id[cows[i].second]=a.second;
			qu.push(b);
		}
	}
	cout<<qu.size()<<endl;
	for(int i=0;i<n;i++){
		cout<<id[i]<<endl;
	}
	return 0;
}

#include #include #include #include #include using namespace std; typedef long long LL; const int MAXN = 1e6 + 10; const int INF = 0x3f; struct cow{ public: int l, r, id; public: void read(int i){ cin >> l >> r; id = i; } private: void debug(){ printf("l = %d,r = %d,id = %d\n", l, r, id); } }cows[MAXN]; int ans[MAXN]; int n; struct greater_q{ bool operator()(cow a, cow b){ return a.r > b.r; } }; priority_queue<cow, vector, greater_q> q; bool cmp(cow a,cow b){ if(a.l == b.l)return a.r < b.r; return a.l < b.l; } int main() { cin >> n; for(int i = 1;i <= n; i++){ cows[i].read(i); } sort(cows + 1,cows + 1 + n, cmp); int cnt = 0; for(int i = 1;i <= n; i++){ if(q.empty() || q.top().r >= cows[i].l){//开启新畜栏 cnt++; ans[cows[i].id] = cnt; q.push(cows[i]); } else{//使用旧畜栏 ans[cows[i].id] = ans[q.top().id]; q.pop(); q.push(cows[i]); } } cout << cnt << endl; for(int i = 1;i <= n; i++){ cout << ans[i] << endl; } return 0; }

#include #include #include #include using namespace std; const int N = 50010; struct node{ int l, r, x; bool operator <(const node& a) const{ if(r == a.r) return l>a.l; return r>a.r; } }a[N];

priority_queue p; int n; bool cmp(node a, node b){ if(a.l == b.l) return a.r<b.r; return a.l<b.l; }

int ans[N]; int main(){ cin>>n; int res = 0; for(int i=1; i<=n; i++){ cin>>a[i].l>>a[i].r; a[i].x = i; } sort(a+1, a+n+1, cmp);

for(int i=1; i<=n; i++){
    if(!p.empty() && p.top().r < a[i].l){
        ans[a[i].x] = ans[p.top().x];
        p.pop();
    }else{
        res++;
        ans[a[i].x] = res;
    }
    p.push(a[i]);
}

cout<<res<<endl;
for(int i=1; i<=n; i++){
    cout<<ans[i]<<endl;
}
return 0;

}