codeforces 523D tatistics of Recompressing Videos

一个称为DH（DogHouse）的狗的社交网络有k台专用服务器来重新上传可爱的猫的上传视频。每个视频上传后，应该在一个（任何）服务器上重新压缩，之后才可以保存在社交网络中。

我们知道每个服务器需要一秒钟来重新压缩一分钟的片段。因此，任何服务器需要m秒钟来重新压缩m分钟的视频。

我们知道每个n个视频上传到网络的时间（从所有服务器开始工作的时间开始）。所有视频都会出现在不同的时刻，并按照他们出现的顺序重新压缩。如果有些视频出现在时间s，那么它的再压缩可以立即从那个时刻开始。当所有服务器都忙时，有些视频可以等待重新压缩。在这种情况下，只要服务器可用，它立即开始重新压缩另一个视频。正在等待重新压缩的视频进入队列。如果视频开始被重新压缩，那么有些服务器可用，那么其中任何一个开始重新压缩视频。

对于每个视频，找到停止重新压缩的那一刻。

输入：

第一行n，k<=5*10^5表示视频数，有k台服务器

接下来n行每行表示一个视频，分别是ai，bi<=10^9。为开始时间与压缩时间

输出：

每个点的最小结束时间

输入

输出

6 
7 
11

输入

6 1 
1 1000000000 
2 1000000000 
3 1000000000 
4 1000000000 
5 1000000000 
6 3

输出

1000000001 
2000000001 
3000000001 
4000000001 
5000000001 
5000000004
数据保证是递增排序的，所以不要排序
所以直接贪心，当堆中满了，选择完成时间最靠前的视频pop
所以堆维护完成时间，算出视频完成时间后加入堆

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long LL;

 struct Node

 {

     LL a,b,num;

 }a[];

 priority_queue<LL, vector<LL>,greater<LL> >q;

 LL n,m,sum,t[];

 LL max(LL a,LL b)

 {

     if (a<b) return b;

     else return a;

 }

 int main()

 {LL i,j;

 //freopen("water.in","r",stdin);

 //freopen("water.out","w",stdout);

     cin>>n>>m;

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

     {

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

         a[i].num=i;

     }

     //sort(a+1,a+n+1,cmp);

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

     {

         if (sum<m)

         {

           sum++;

            q.push(a[i].a+a[i].b);

            t[i]=a[i].a+a[i].b;

         }

         else

         {

             LL tmp=q.top();

             q.pop();

             q.push(max(tmp,a[i].a)+a[i].b);

             t[i]=max(tmp,a[i].a)+a[i].b;

         }

     }

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

     printf("%I64d\n",t[i]);

 }

巴特西

codeforces 523D tatistics of Recompressing Videos

最新文章

热门文章