同一时间段同时工作问题
可以类比木棍问题,本题坑比较多
1.输入数据要判断哪个是起点,哪个是终点
2.排序时要按照起点排序 (有特殊情况)
1
4
2 4
1 6
10 12
5 14
终点排序结果是30,起点是20
3.注意终点的奇偶性,奇数与其+1共用一段走廊,判断时候要考虑终点是奇数还是偶数
就是你每次要尽可能的同时进行多次工作，直到完成所有工作
AC代码：
#include <stdio.h> #define N 201 typedef struct Locate {int from;int to;int visit; }Loc; Loc loc[N]; void quick_Sort(Loc p[],int left,int right) {int i=left,j=right;int pivot=p[(i+j)/2].from;Loc temp;while (i<=j){while(p[i].from<pivot){i++;}while (p[j].from>pivot){j--;}if (i<=j){temp=p[i];p[i]=p[j];p[j]=temp;i++;j--;}}if(left<j) quick_Sort(p,left,j);if(i<right) quick_Sort(p,i,right); } int find(int n) {int sum=0,temp=0;for(int i=1;i<=n;i++){if(loc[i].visit==0){temp=i;sum++; //sum代表你能你经历了几次循环loc[i].visit=1;for(int j=1;j<=n;j++){if(loc[j].visit==0&&((loc[temp].to%2==1&&loc[j].from>loc[temp].to+1)||(loc[temp].to%2==0&&loc[j].from>loc[temp].to))) //可以同时移动（不要忘了考虑终点的奇偶性吖）{temp=j;loc[j].visit=1;}}}}return sum*10; } int main() {int T,n;int from,to;scanf("%d",&T);while (T--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %d",&from,&to);loc[i].from=from<to?from:to;loc[i].to=from>to?from:to;loc[i].visit=0;}if(n==1){printf("10\n");continue;}quick_Sort(loc,1,n);printf("%d\n",find(n));}return 0; } // poj 1083