洛谷 T2691 桶哥的问题—

嗯...

题目链接：https://www.luogu.org/problem/T2691

这道题有一点贪心的思想吧...并且思路与题目是倒着来的（貌似这种思路已经很常见的...

先举个栗子：

引出思路：按结束时间早晚排序，因为没有多早的限制，但是最晚送到的时间却有限制。把时间倒流，把时间轴倒着看，首先t初始化为max(b[i])，然后枚举一遍，如果当前t大于b[i]，那在t的时候不可能到达，所以要把t改为b[i]。并且t要减去消耗时间a[i]。

初始值为最后一个送到的时间，往前推，如果前面的一个送餐时间限制比后面的时间节点（例如F）减去送餐时间（EF）晚的话，那么就把前一段送餐时间用减去，因为在两个重合（GH和EF）时间段内，在实际情况下不可能同时送两个餐，那么最紧凑的排列方法就是往前挨着叠加，那么t就变成了F（横坐标）减去EF和GH的长度，得到一个新的横坐标,再往前和前一个完成时间限制点（B）比较，看哪个更晚。

如果后面的时间节点（例如F）减去送餐时间（EF）比前面的一个送餐时间限制晚的话，就意味着最短时间限制提前到了当前的时间限制点，因为只要安排得当的话，从当前时间限制点以后的时间不会对最早时间造成任何影响！那么我们就把t提前到当前的时间限制点，继续往前推就行了。

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 //时间倒流

 using namespace std;

 const int maxn = 1e6 + ;

 int n;

 struct node{

     int a, b;

 } e[maxn];

 inline bool cmp(node x, node y){

     return x.b > y.b;

 }

 int main(){

     scanf("%d", &n);

     for(int i = ; i <= n; i++)

         scanf("%d%d", &e[i].a, &e[i].b);

     sort(e + , e +  + n, cmp);

     int t = e[].b;

     for(int i = ; i <= n; i++){

         if(t > e[i].b) t = e[i].b;

         t -= e[i].a;

     }

     printf("%d\n", t);

     return ;

 }

AC代码

巴特西

洛谷 T2691 桶哥的问题——送桶

嗯...

题目链接：https://www.luogu.org/problem/T2691

这道题有一点贪心的思想吧...并且思路与题目是倒着来的（貌似这种思路已经很常见的...

AC代码：

最新文章

热门文章