题目大意：农夫有N只牛，这些牛要帮助打扫农舍，这些牛只能打扫固定位置（千万要注意这个位置不是连续的），每一段区间必须至少有一只牛打扫，问你至少需要多少只牛？（如果区间不能完全被覆盖，则输出-1）。
这一题有点像上次的萨鲁曼军队，就是一个区间贪婪算法，我们尽可能的由一个方向往前找到最大的区间就可以了（如果与本位置的endT的间隔相同，找最远的，贪婪的最基本的思想）。
这一题本身不难，但是特判很恶心，一不小心就要出错了，比如1 5 3 1这样的输入，就直接输出-1就可以了（一定要有牛打扫1），还有，更关键的是，区间是不连续的（也就是扫完了13，下一次还可以扫46），一定要注意这一点！
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 5 using namespace std; 6 typedef struct cows_t 7 { 8 int start_T; 9 int end_T; 10 }Cow_Set; 11 12 Cow_Set cows[25000]; 13 void Search(const int, const int); 14 int fcmop(const void *a, const void *b) 15 { 16 return (*(Cow_Set *)a).start_T - (*(Cow_Set *)b).start_T; 17 } 18 19 int main(void) 20 { 21 int N, T; 22 while (~scanf("%d%d", &N, &T)) 23 { 24 for (int i = 0; i < N; i++) 25 scanf("%d%d", &cows[i].start_T, &cows[i].end_T); 26 qsort(cows, N, sizeof(Cow_Set), fcmop); 27 Search(N, T); 28 } 29 30 return 0; 31 } 32 33 void Search(const int N, const int T) 34 { 35 int et = 1, pos = 0, tmp_pos = -1, ans = 0, tmp_maxt, j; 36 if (cows[0].start_T != 1) 37 { 38 cout << -1 << endl; 39 return; 40 } 41 while (1) 42 { 43 if (cows[pos].start_T > et + 1)//说明没有牛可以突破当前这个上一个时间界限，不用找了 44 { 45 cout << -1 << endl; 46 return; 47 } 48 ans++;//增加一头开始的那头牛 49 if (cows[pos].end_T >= T) 50 break; 51 tmp_maxt = 0; tmp_pos = pos; 52 for (j = pos + 1; j < N && (cows[j].start_T <= cows[pos].end_T + 1); j++)//找到间隔比当前T还要长的牛(记得T可以间隔1) 53 { 54 if (cows[j].end_T - cows[pos].end_T >= tmp_maxt)//要带等号，尽量往前 55 { 56 tmp_pos = j; 57 tmp_maxt = cows[j].end_T - cows[pos].end_T; 58 } 59 } 60 if (tmp_pos == pos) 61 { 62 cout << -1 << endl; 63 return; 64 } 65 pos = tmp_pos; 66 et = cows[tmp_pos].start_T; 67 } 68 if (ans != 0) 69 printf("%d ", ans); 70 else 71 cout << -1 << endl; 72 }
