Milking Cows区间计数 离散化排序 oj10105

题目大意： 输入n  接下来描述1~n位农夫挤牛奶的开始与结束时间   Sample Input

3300 1000700 12001500 2100

Sample Output

900 300

 

注意开始结束时间都可能相同 且不一定是按时间顺序的

题解：http://www.xuebuyuan.com/1960543.html

 

#include <bits/stdc++.h> using namespace std; struct COW{ int tm,k; }cow[10005]; bool cmp(COW a,COW b) { if(a.tm==b.tm) return a.k>b.k; return a.tm<b.tm; } int main() { int n; while(~scanf("%d",&n)) { int j=1; while(n--) { scanf("%d",&cow[j].tm); cow[j++].k=1; scanf("%d",&cow[j].tm); cow[j++].k=0; } sort(cow+1,cow+j,cmp); int key,last,lcon,lid; key=last=lcon=lid=0; for(int i=1;i<j;i++) { if(cow[i].k) key++; else key--; if(!key) { lcon=max(lcon,cow[i].tm-cow[last+1].tm); lid=max(lid,cow[i+1].tm-cow[i].tm); last=i; } } printf("%d %d\n",lcon,lid); } return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8670013.html