本题可理解为用N个线段去覆盖1-T的数轴，求最少使用的线段数。贪心算法每次都取当前的最佳值，适用本题。不少人想当然，认为每次用最长的线段来填，直到填满。举个反例：T为10，N为5，（1，2）、（3，8）、（9，10）、（1，6）、（6，10），按照上面的思路则取线段顺序为（3，8）、（1，6）、（6，10），需要3条线段，这并不是最短的。其实，每次应在满足条件的情况中选取终点最大的那条，如此则选（1，6）、（6，10）就够了。值得一提的是本题端点间的区间不需要覆盖，如（1，2）、（3，8）可以完全覆盖（1，8）。原题链接
#include <stdio.h> #include <algorithm> #include <utility> const int maxn=25001; using namespace std; int main(){ int N,T,k=0,pos=0 ; ///pos初始为0，当作前面一个区间的末尾 pair<int,int> cow[maxn]; ///存储每个区间的始末点 scanf("%d %d",&N,&T); while(N--) { scanf("%d %d",&cow[k].second,&cow[k].first); ///second是起点，first是终点，便于排序 k++; } sort(cow,cow+k); ///sort()是key值从小到大排序 int ans=0; while(pos<T){ int id=0; for(int i=k-1;i>=0;i--) if(pos+1>=cow[i].second){ ///注意，两个shift之间不必覆盖 pos=cow[i].first; cow[i].second=T+1; ///用完后，起点置为不可到达的数 ans++;id=1; break; } if(!id) {ans=-1;break;} ///若区间断了，则不能满足题目条件 } printf("%d\n",ans); return 0; }
