题目链接
题目大致是说有一群奶牛要挤牛奶，但是她们只在规定的时间区间内挤牛奶，而且一台挤奶机只能给一头牛挤牛奶，问最少需要几台挤奶机才能给全部的牛挤牛奶，并且输出每头牛是在第几台挤奶机挤的牛奶，第一行输入奶牛数，然后按顺序输入每头奶牛的挤牛奶时间区间。输出则是第一行输出最少的挤奶机数。然后一次输出每头奶牛是在第几台挤奶机挤的奶。首先对挤牛奶区间sort一下，优先按区间左端点从小到大sort，然后在左端点相同的情况下按右端点从下到大排序，然后flag记录每头奶牛对应的挤奶机标号。对优先队列的<号重载实现优先将队列中右端点较小者返回。然后再模拟安排过程(即优先放起始时间早的，若现在有空闲的挤奶机则放在这台挤奶机挤奶，否则另外再开一台)即可。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> using namespace std; struct node { int a; int d; int num; node() { a=0; d=0; num=0; } bool operator < (const node &t)const { if(d==t.d)return a>t.a; return d>t.d; } } s[50005]; bool cmp(node x,node y) { if(x.a!=y.a)return x.a<y.a; return x.d<y.d; } priority_queue<node> q; int flag[50005]={0}; int main() { //freopen("in.in","r",stdin); int n; while(scanf("%d",&n)!=EOF) { memset(s,0,sizeof(0)); memset(flag,0,sizeof(flag)); for(int i=0; i<n; i++) { scanf("%d%d",&s[i].a,&s[i].d); s[i].num=i; } sort(s,s+n,cmp); /*for(int i=0;i<n;i++) printf("%d %d\n",s[i].a,s[i].d);*/ while(!q.empty())q.pop(); flag[s[0].num]=1; q.push(s[0]); int ans=1; for(int i=1;i<n;i++) { if(q.top().d<s[i].a)//此处是<号而不是<=号，不然会跪 { flag[s[i].num]=flag[q.top().num]; q.pop(); }else { ans++; flag[s[i].num]=ans; } q.push(s[i]); } printf("%d\n",ans); for(int i=0;i<n;i++) printf("%d\n",flag[i]); } return 0; }
