• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021牛客暑期多校训练营6

admin

11月 28, 2021

F Hamburger Steak

考场上打自闭的一道构造题…

先考虑若每个汉堡都能无限拆分的话,那我们很容易想到将所有汉堡的时间加起来均分到每个锅里面,答案就是sum/m向上取整。但这个题中规定每个汉堡只能拆分成两个,其实我们考虑均分的时候我们不必真的将每个汉堡都拆成若干个1,我们只需要将当前锅的时间段弄满,若超过的话我们再将其拆开就行,同时题中规定,同一个汉堡不能在同一个时间段被两个锅同时做,所以我们考虑一个汉堡拆开后的情况,在一个锅中时间段弄完,又到另一个锅中,时间段又不能和上一个时间段重合,所以我们可以断定这个汉堡的纵向长度起码是t[i],所以结合以上两点我们可以得知总的用时为max(maxt[i],sum/m向上取整)。之后考虑怎么分配每个汉堡,总体的思路就是想将每个锅的用时T求出来,依次向每个锅里面扔汉堡,若当前锅的时间now+t[i]>T的话说明当前汉堡不能完整的放入这个锅里,我们就将其拆分成两个将其放到另一个锅中,因为保证了T>=maxt[i]所以一个从零开始的锅一定能放下一个未完整的汉堡。但有可能出现这个汉堡另一个锅的时间段和这个锅的时间段重合,但其实考虑若真出现这种情况的话,说明这个汉堡的t[i]要大于T才行,但这显然是和上面不符的,我们大胆放心的用就行了。

//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define P 1000000007
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
#define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=1e5+10;
int n,m;
ll t[N];
 
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
 
int main()
{
//    freopen("1.in","r",stdin);
    get(n);get(m);
    ll sum=0,T,mx=0;
    rep(i,1,n) 
    {
        get(t[i]);
        sum+=t[i];mx=max(mx,t[i]);    
    }
    T=max(mx,(sum%m)?(sum/m+1):(sum/m));
    int now=1;
    ll last=0;
    rep(i,1,n)
    {
        if(last+t[i]<=T)
        {
            printf("%d %d %lld %lld
",1,now,last,last+t[i]);
            last+=t[i];
        }
        else
        {
            printf("%d %d %lld %lld %d %lld %lld
",2,now+1,0,t[i]-(T-last),now,last,T);
            now++;last=t[i]-(T-last);
        }
        if(last==T) now++,last=0;
    }
    return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.

View Code

发表回复

您的电子邮箱地址不会被公开。