题目链接

题目大意

给你n个生肉和m个锅,每份肉需要煎t_i时间,但是你可以把t_i分成a_i+b_i两段时间来做。一块肉最多只能分成两次来做,现在要求总时间最少,请你输出安排方案(n行,每行输出用1or2个锅,锅的id,煎的时段[l,r])

解题思路

水题,本来我是第一个读到的但是没有考虑完整,所以一直觉得有问题。

实际上本题只需要模拟即可。最大耗时一定是max(耗时最长的肉,每个锅煎肉的平均值)。因为耗时最长的肉不管怎么分,一定都会消耗那么长的时间。

之后模拟整个过程按顺序填入锅内即可。如果一口锅填满了就换下一个,因为上面求得的最大耗时一定≥每一条肉的耗时,因此把肉分成两段一定是可以填满的。

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+7;
const int eps = 1e-8;
const int inf = 0x7f7f7f7f;
const int mod = 1e9+7;
int T;
int n,m,k;
int a[N];
struct steak{
    int times;//用了1个还是2个锅
    int l,r,pan;//第一口锅的端点和序号
    int ll,rr,ppan;//第二口锅的端点和序号
    int num,id;//肉的序号和长度
}z[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int avg=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        z[i].id=i;
        z[i].num=a[i];
        avg+=a[i];
        T=max(T,a[i]);
    }
    avg=(avg+m-1)/m;
    T=max(avg,T);//一定是均值或最长的肉
    int pos=1;//肉的下标[1,n]
    int p=0;//当前这口锅已经用了多久
    int i=1;//锅的下标[1,m]
    while(i<=m && pos<=n){
        if(a[pos]+p<T){
            z[pos].times=1;
            z[pos].l=p;
            z[pos].r=p+a[pos];
            z[pos].pan=i;
            p+=a[pos];
            pos++;
        }
        else if(a[pos]+p==T){
            z[pos].times=1;
            z[pos].l=p;
            z[pos].r=T;
            z[pos].pan=i;
            i++;
            p=0;
            pos++;
        }
        else{
            z[pos].times=2;
            z[pos].l=p;
            z[pos].r=T;
            z[pos].pan=i;
            z[pos].ll=0;
            z[pos].rr=a[pos]-(z[pos].r-z[pos].l);
            z[pos].ppan=i+1;
            i++;
            p=a[pos]-(z[pos].r-z[pos].l);
            pos++;
        }
    }
    for(int i=1;i<=n;i++){
        if(z[i].times==1) cout<<z[i].times<<" "<<z[i].pan<<" "<<z[i].l<<" "<<z[i].r<<endl;
        if(z[i].times==2) cout<<z[i].times<<" "<<z[i].ppan<<" "<<z[i].ll<<" "<<z[i].rr<<" "<<z[i].pan<<" "<<z[i].l<<" "<<z[i].r<<endl;
    }
    return 0;
}

分类: 补题

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注