USACO Section 4.2 Job Processing - 贪心

网友投稿 287 2022-08-25

USACO Section 4.2 Job Processing - 贪心

首先看第一问...因为每个机器是独立工作的...那若要时间最小..每个机器在使用过程中是不会休息的..也就是做完了上一个马上做下一个..直到不用这个机器为止..那么显然最大时间就是使用时间最长的机器..为了得到这个结果..用一个数组记录当前每个机器使用到了哪个时间...从第1个工件开始做到第N个..做的时候贪心判断..这个工件放在哪个A机器做能使所有机器中的最大使用时间最小...找到了后就将工件放到那个机器..并更新这个机器的使用时间...如此做下去就能得到第一问的答案..并且将所有工件成毛坯的时间_timeA[ i ]纪录下,并从小到大排号序..来第二问要用到...

第二问首先对B做同样的贪心..得到每个工件的处理时间_timeB[ i ]..并从小到大排好序..然后用最大的判断_timeA[ i ] + _timeB [ n - i + 1 ]的最大值..既是答案..这里我是想着大的和小的结合..小的和大的结合..这样总的来说就是比较平均的..那么最晚出来的工件时间也会是所有使用情况中最快的..就这么写了..就这么过了.但感觉还是不够严谨..

Program:

/* ID: zzyzzy12 LANG: C++ TASK: job*/ #include #include #include #include #include #include#include#include #include #define oo 1000000000 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std;int n,m1,m2,A[35],B[35],_timeA[1005],_timeB[1005];void getanswer1(){ int m=n,i,k,dp[35]; memset(dp,0,sizeof(dp)); while (m--) { k=1; for (i=2;i<=m1;i++) if (dp[k]+A[k]>dp[i]+A[i]) k=i; dp[k]+=A[k]; } k=0; for (i=1;i<=m1;i++) if (kdp[i]+B[i]) k=i; dp[k]+=B[k]; } m=0; for (i=1;i<=m2;i++) for (k=B[i];k<=dp[i];k+=B[i]) _timeB[++m]=k; sort(_timeB+1,_timeB+1+n); ans=0; for (i=1;i<=n;i++) if (_timeA[i]+_timeB[n-i+1]>ans) ans=_timeA[i]+_timeB[n-i+1]; printf("%d\n",ans); return;}int main() { freopen("job.in","r",stdin); freopen("job.out","w",stdout); scanf("%d%d%d",&n,&m1,&m2); for (int i=1;i<=m1;i++) scanf("%d",&A[i]); for (int i=1;i<=m2;i++) scanf("%d",&B[i]); getanswer1(); getanswer2(); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

上一篇:队内赛我出的一道题附标程、数据与解题报告
下一篇:“咖啡店停业”引热议，碰瓷营销该停停了！
相关文章

 发表评论

暂时没有评论，来抢沙发吧~