本文共 909 字,大约阅读时间需要 3 分钟。
最近在学习算法,c++还有好多知识不会,想慢慢通过算法来熟悉,如果有题讲解的不好或是代码写的不好还请大家多多指教。
题意:给你N头牛和工作的时间区域T(1~T),每头牛都有工作的开始时间和结束时间,代码里分别用cows[i].begin和cows[i].end表示,选择尽可能少的奶牛完成清洁工作,如果不可能分配的话,打印-1
思路:这道题是一个区间贪心的问题,对给的牛工作时间进行排序,开始时间小的排在前面,开始时间一样的,结束时间小的排在前面。然后进行贪心
误区:3 10
1 5
6 10
10 10
这个最后的结果是2,而不是-1.它可以是连续的(1~6)(6~10),也可以是(1~5)(6~10),所以每回与上个数比较的时候是与(结束时间+1)进行比较而不是与上一个结束时间比较
#include #include using namespace std;const int N_max=25100;struct times{ int begin,end;}cows[N_max];bool cmp(times a,times b){ if(a.begin==b.begin) return a.end >cows[i].begin>>cows[i].end; } sort(cows+1,cows+1+N,cmp); if(cows[1].begin!=1){ cout<<"-1\n"< cows[id].end+1) break; if(cows[j].begin>=cows[id].begin&&cows[j].end>=cows[id].end+1){ if(cows[j].end>cows[cnt].end) cnt=j; } } if(cnt==0) i++; else{ id=cnt; ans++; i=id; } } if(cows[id].end==T) cout< <
转载地址:http://xkxhj.baihongyu.com/