emmmmm

显然，我太水了

（已经开始不会做橙题了www

【嚎啕大哭

（emmmm其实知道这是贪心之后就很好想了

emmm

马拉松这道题呢

每个人都有基础的1km

这样就分剩下的20km就好了

然后用贪心的思想

因为没有所谓后效性

每次取下1km跑的时间最短，即跑得最快的人

然后一直到20km分完

en

看代码吧

#include
     
      #include
      
       using namespace std;int a[5][11],b[5][11]; int c[5]; int main(){ int flag,ans = 0; c[0] = c[1] = c[2] = c[3] = c[4] = 1;//每个人基础有1km for(int i = 0;i < 5;i++) for(int j = 1;j <= 10;j++){ scanf("%d",&a[i][j]); b[i][j] = a[i][j] - a[i][j - 1];//提前算出来每个人每千米用的时间 } for(int i = 0;i < 20;i++){ int minn = 2147483647; for(int j = 0;j < 5;j++) if(b[j][c[j] + 1] < minn && c[j] + 1 <= 10){ flag = j;//记一下哪个人 minn = b[j][c[j] + 1];//记一下多短的 } c[flag] ++;//当前这km跑得最快的人km数加一 } for(int i = 0;i < 5;i++) ans += a[i][c[i]]; printf("%d\n%d %d %d %d %d",ans,c[0],c[1],c[2],c[3],c[4]); return 0; }
      
     

啊好的我们来看线段覆盖

（真是令人绝望啊wwww

也是贪心en

按右端点大小排序，每次取最左的一条使剩下的右边的线段可以最多

（请意会吧。。。

（啊然后来叨叨一下我神奇的思路

（先按左端点排序，存到一个数组里，然后一组一组求最长不下降自序列

（emmmm我自己不会实现

（然后可以想见的时间复杂度233333

好哒来看正常贪心代码

#include
     
      #include
      
       #include
       
        using namespace std;#define maxn 1000010struct LINE{  int l,r;}line[maxn];int cmp(LINE x,LINE y){  return x.r < y.r;}int main(){  int n;  scanf("%d",&n);  for(int i = 1;i <= n;i++){    int l,r;    scanf("%d%d",&l,&r);    if(l > r)      swap(l,r);//不知道有没有用先写上。。。我没仔细看题干    line[i].l = l;    line[i].r = r;  }  sort(line + 1,line + 1 + n,cmp);  int last = -1;//从零开始的时间所以第一次设为-1  int ans = 0;//计数  for(int i = 1;i <= n;i++){    if(line[i].l >= last){
   //下一条线段是否覆盖      ans++;      last = line[i].r;//更新last    }  }  printf("%d",ans);  return 0;}
       
      
     

emmmm

就这样结束啦

还是很不明白自己为什么这么菜www

【哭唧唧

事实证明luogu标签真的在一定程度上使做题思路更好想

orz