首页 > 代码库 > 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