随笔-141  评论-9  文章-3  trackbacks-0

1. 用贪心分别算出A单独加工n个工件的时间f1, 和B单独加工n个工件的时间f2

2. 用f1 的最小值 + f2 最大值 , 用平均贪心的思想. 再比较最大值为第二问的解.

/*
ID: lorelei3
TASK: job
LANG: C++
*/


#include 
<fstream>
#include 
<algorithm>
#include 
<functional>

using namespace std;

const int MAXN = 1005;
const int MAXM = 35;

int t1[MAXM], t2[MAXM], w1[MAXM], w2[MAXM], f1[MAXN], f2[MAXN];

int main(){
    
int i,j, n, m1, m2;

    ifstream fin(
"job.in");
    ofstream fout(
"job.out");

    fin
>>n>>m1>>m2;

    
for(i=1; i<=m1; ++i)
        fin
>>t1[i];

    
for(i=1; i<=m2; ++i)
        fin
>>t2[i];

    
for(i=1; i<=n; ++i){
        
int min=1
        
for(j=2; j<=m1; ++j)
            
if(w1[j]+t1[j] < w1[min]+t1[min])
                min
=j;
        w1[min] 
+= t1[min];
        f1[i] 
= w1[min];

        min
=1;
        
for(j=2; j<=m2; ++j)
            
if(w2[j]+t2[j] < w2[min]+t2[min])
                min 
=j;
        w2[min] 
+= t2[min];
        f2[i] 
= w2[min];
    }


    sort(f1
+1, f1+n+1, less<int>());
    sort(f2
+1, f2+n+1, greater<int>());

    
int ans1 = f1[n], ans2 = 0;

    
for(i=1; i<=n; ++i)
        
if(f1[i]+f2[i] > ans2)
            ans2 
= f1[i]+f2[i];

    fout
<<ans1<<" "<<ans2<<endl;



    
return 0;
}
posted on 2011-01-25 17:10 小阮 阅读(795) 评论(2)  编辑 收藏 引用 所属分类: USACO

评论:
# re: USACO 4.2.3 Job Processing (平均贪心) 2012-06-01 14:25 | 怡红公子
平均的贪心,好像没听说诶。  回复  更多评论
  
# re: USACO 4.2.3 Job Processing (平均贪心) 2015-08-05 16:01 |
如何证明其正确性  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理