本文共 1718 字，大约阅读时间需要 5 分钟。
http://poj.org/problem?id=2376
john有n头牛做打扫工作，他想在t时间内每个时间都至少有一头牛在做打扫工作，第一头牛在1，最后一头牛在t时间，每一头牛工作都有一个开始时间和结束时间，现在让我们找出在每个时间点都有牛打扫的情况下，所用牛越少越好，不能满足输出-1.
首先按起点排序，起点相同就按结束时间长的排序，然后贪心，每次选择时满足 当前牛的开始时间<=上一头牛的结束时间加1，并且当前牛的结束时间最大的一个。
注意 ： 不必覆盖只要能连接即可。（1 3 4 6） 是可以的！！！
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 17 #define CL(arr, val) memset(arr, val, sizeof(arr))18 19 #define ll long long20 #define inf 0x7f7f7f7f21 #define lc l,m,rt<<122 #define rc m + 1,r,rt<<1|123 #define pi acos(-1.0)24 25 #define L(x) (x) << 126 #define R(x) (x) << 1 | 127 #define MID(l, r) (l + r) >> 128 #define Min(x, y) (x) < (y) ? (x) : (y)29 #define Max(x, y) (x) < (y) ? (y) : (x)30 #define E(x) (1 << (x))31 #define iabs(x) (x) < 0 ? -(x) : (x)32 #define OUT(x) printf("%I64d\n", x)33 #define lowbit(x) (x)&(-x)34 #define Read() freopen("a.txt", "r", stdin)35 #define Write() freopen("b.txt", "w", stdout);36 #define maxn 100000000037 #define N 101038 using namespace std;39 40 struct point41 {42 int x,y;43 }p[25010];44 bool cmp(const point &a,const point &b)45 {46 if(a.x!=b.x) return a.x b.y;48 }49 int main()50 {51 //Read();52 //Write()53 int n,t;54 while(~scanf("%d%d",&n,&t))55 {56 for(int i=0;i max)73 {74 flag=1;75 j=i;76 max=p[i].y;77 }78 }79 if(!flag) break;80 //printf("%d %d\n",p[j].x,p[j].y);81 ans++;82 if(max==t)83 {84 printf("%d\n",ans);85 flag=1;86 break;87 }88 m=max;89 }90 if(!flag||max
转载于:https://www.cnblogs.com/nowandforever/p/4408726.html
