网站域名备案后公示,ppt模板免费下载完整版免费无需会员,浙江seo技术培训,网站内容建设与管理Hamburger Steak
题意#xff1a;
有m个锅#xff0c;n块肉#xff0c;每个肉需要煎ai分钟才能熟#xff0c;每个锅同时最多煎一块肉#xff0c;一块肉最多可以被两个锅煎(但不能同时)#xff0c;问最少多长时间能全部煎熟#xff0c;并输出方案
题解#xff1a;
我…Hamburger Steak
题意
有m个锅n块肉每个肉需要煎ai分钟才能熟每个锅同时最多煎一块肉一块肉最多可以被两个锅煎(但不能同时)问最少多长时间能全部煎熟并输出方案
题解
我一开始的想法是二分每个锅最长用的时间然后顺序煎每个肉如果这个肉还没煎完这个锅的时间用完了就到下一个锅继续煎顺序输出完事。需要保证所有锅的时间和大于等于所有肉需要的时间 后来发现其实最小耗时不用二分直接算出来的Tmax{max{ti},|∑ti\sum{ti}∑ti/m|},
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_txt(){#ifdef ONLINE_JUDGE#elsefreopen(in.txt,r,stdin);#endif
}
int n,m;
const int maxn3e59;
ll a[maxn];
bool check(ll x){ll sum0; ll tot1;for(int i1;in;i){suma[i];if(sumx){tot;sumsum-x;}}if(totm)return 0;return 1;
}int main()
{rd_txt();cinnm;ll l0,r0;for(int i1;in;i){cina[i];lmax(a[i],l);ra[i];}rr*2;while(lr){ll midlr1;if(check(mid))rmid;else lmid1;}//coutllendl;ll sum0;ll tot1;ll L0;for(int i1;in;i){if(La[i]l){printf(2 %lld %lld %lld %lld %lld %lld\n,tot1,0,La[i]-l,tot,L,l);tot;LLa[i]-l;}else {printf(1 %lld %lld %lld\n,tot,L,La[i]);La[i];}if(Ll){L0;tot;}}
}
