首页 > 代码库 > usaco-4.2-job-passed
usaco-4.2-job-passed
初看真以为是网络流呢,实际上应是贪心算法,最简洁的算法:
/*ID: qq104801LANG: C++TASK: job*/#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>using namespace std;const int inf=1<<30;const int nmax=35;int n;int a[nmax],b[nmax];int sa[nmax],sb[nmax];int cost_a[nmax*nmax],cost_b[nmax*nmax];void test(){ freopen("job.in","r",stdin); freopen("job.out","w",stdout); int temp1,temp2; cin>>n>>a[0]>>b[0]; for(int i=1;i<=a[0];i++) cin>>a[i]; for(int i=1;i<=b[0];i++) cin>>b[i]; int i,j,k,t; for(t=1;t<=n;t++) { k=inf; for(i=1;i<=a[0];i++) if(sa[i]+a[i]<k) k=sa[i]+a[i],j=i; cost_a[t]=sa[j]=k; k=inf; for(i=1;i<=b[0];i++) if(sb[i]+b[i]<k) k=sb[i]+b[i],j=i; cost_b[t]=sb[j]=k; } sort(cost_a,cost_a+n); sort(cost_b,cost_b+n); for(k=i=1;i<=n;++i) k=max(k,cost_a[i]+cost_b[n-i+1]); cout<<cost_a[n]<<" "<<k<<endl;}int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 19 users onlineBRA/1 CHN/8 IND/1 TJK/1 TWN/1 USA/7USER: cn tom [qq104801]TASK: jobLANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.008 secs, 3384 KB] Test 2: TEST OK [0.005 secs, 3384 KB] Test 3: TEST OK [0.003 secs, 3384 KB] Test 4: TEST OK [0.003 secs, 3384 KB] Test 5: TEST OK [0.003 secs, 3384 KB] Test 6: TEST OK [0.003 secs, 3384 KB] Test 7: TEST OK [0.003 secs, 3384 KB] Test 8: TEST OK [0.003 secs, 3384 KB] Test 9: TEST OK [0.003 secs, 3384 KB] Test 10: TEST OK [0.003 secs, 3384 KB] Test 11: TEST OK [0.005 secs, 3384 KB] Test 12: TEST OK [0.003 secs, 3384 KB]All tests OK.Your program (‘job‘) produced all correct answers! This is your submission #2 for this problem. Congratulations!Here are the test data inputs:------- test 1 ----5 2 31 13 1 4------- test 2 ----2 2 23 58 5------- test 3 ----10 1 212 3------- test 4 ----10 2 13 1910------- test 5 ----10 1 5156 2 4 4 20------- test 6 ----10 5 16 20 9 8 122------- test 7 ----100 2 22 32 3------- test 8 ----100 5 518 15 4 2 64 8 9 2 3------- test 9 ----100 10 107 20 7 3 16 8 16 10 4 13 5 7 2 18 5 13 8 4 7------- test 10 ----1000 2 31 12 6 7------- test 11 ----1000 2 18 513------- test 12 ----1000 30 3015 15 2 1 13 2 1 15 12 2 3 16 15 5 13 6 17 14 17 2 9 9 13 12 14 8 2 8 12 119 2 20 6 2 10 16 9 13 6 13 18 9 1 7 14 5 2 5 14 1 13 11 2 4 17 8 20 8 19Keep up the good work!Thanks for your submission!
usaco-4.2-job-passed
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。