学校oj有这道题,感觉这不需要多复杂,只是一个贪心(构造也不难)。
Special Judge有多种解题思路,我只说一种(看不到原题,错误谅解)。
上限
贪心,顾名思义啥都能要,这道题可以将 每个锅当成桶,将烤面包的时间当成所占的空间,然后将面包一个一个装进去(而且还能掰开放进两个桶里)
但如果我们这样做的话,是需要桶的空间上限,那这个上限是多少呢?这关乎整个思路的正确性,因为要尽可能快的烤完,所以上限应该是所有面包烤完的时间平均分配给每个桶,则:sum+=t[i];
但是仅为这个上限的话,会遇到特殊情况,比如一大堆时间都是1,仅有一个为10,这样可能会拉长时间,从而使答案错误,所以应该再在这些数中取得一个最大值:maxx=max(maxx,t[i]),使得时间更加富裕,结果也正确。
上限就取max(maxx,sum/m),即为上限。
整体思路
拿样例来说吧
5 3
1 2 3 4 5
三个桶 ,那上限就是5,直接上图
这样就大概明白了,这个桶用完了就换下一个桶,思路简单,代码暴力:(上面有注释)
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
long long n,m,t[N],sum,maxx;
struct T{
long long id,t;
}a[N];
struct ANS{
long long i,k,id[5],l[5],r[5];
}ans[N];
int main(){
freopen("hamburger.in","r",stdin);
freopen("hamburger.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i].t);
a[i].id=i;
sum+=a[i].t;
maxx=max(maxx,a[i].t);
}
maxx=max(maxx,(sum)/m); //上限(桶的空间)
long long bh=1,max_bh=maxx; //bh是第几个桶,max_bh指该桶还剩多少空间
for(int i=1;i<=n;i++){
if(a[i].t<=max_bh){ //如果一个桶能装下
ans[i].k=1;
ans[i].id[1]=bh;
ans[i].l[1]=maxx-max_bh; //左边界
ans[i].r[1]=maxx-max_bh+a[i].t; //右边界
max_bh-=a[i].t;
if(max_bh==0){ //没空间了,直接下一个桶
max_bh=maxx; //回归maxx
bh++;
}
}else{ //装不下分两次来装
ans[i].k=2;
ans[i].id[1]=bh;
ans[i].l[1]=maxx-max_bh; //左边界同上
ans[i].r[1]=maxx; //有边界即为上限
a[i].t-=max_bh; //面包所需时间减少
max_bh=maxx; //回归maxx
bh++;
ans[i].id[2]=bh;
ans[i].l[2]=0; //左边界为0(刚开始)
ans[i].r[2]=a[i].t; //有边界为面包剩余所需时间
max_bh-=a[i].t;
}
}
for(int i=1;i<=n;i++){
if(ans[i].k==1){ //如果一个桶装下了
printf("%lld %lld %lld %lld\n",ans[i].k,ans[i].id[1],ans[i].l[1],ans[i].r[1]);
}else{ //没装下
printf("%lld %lld %lld %lld %lld %lld %lld\n",ans[i].k,ans[i].id[2],ans[i].l[2],ans[i].r[2],ans[i].id[1],ans[i].l[1],ans[i].r[1]); //先输出时间靠前的
}
}
return 0;
}