首页 > 其他 > 详细

UVALive3971组装电脑

时间:2014-01-15 23:53:37      阅读:512      评论:0      收藏:0      [点我收藏+]

UVALive3971

 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3276

题目描述:组装电脑

总共有b元钱,给定n电脑配件信息{种类;名称;价格;品质因子}。目标是用给定的b元钱,在每个种类中选择一个配件购买,统计所购买的配件中最低的品质因子MIN,我们的目标是使这个MIN最大。约束条件是分属每种类配件至少买一个。

解题思路:

运筹三要素分析:

决策方案:

假设每种类配件的数目是{a1a2........an},方案数是a1*a2......an

约束条件:

A:总价格不超过b元;

目标评判标准:

B:最小的品质因子最大;

在上面分析的方案中,通过A可剔除一部分,通过B确定最优解;

算法分析:

这道题目的问题在于,备选答案是线性分布的即{0......maxq}都可能是最优解,所求又是最大的最小值,所以使用二分。还有一个关键的问题,对于枚举的最低品质因子x,每种配件买品质因子至少为x,价格最低的就可以了。具体实现参考代码。

PS有的题目是分析方案很难,有的是设计快速找到最优解的方法难,这道题是后者。

代码分析:

1、难点一:信息的表示,用mapvector存储,其实vector(元素为每种类的配件集合)可以用数组实现,这样就要记录每种类的配件个数,读数据时会很麻烦

2、难点二:二分不超时,现在我的办法是手动画状态图,满足:a.枚举到aim;b.可跳出循环

全部代码:

 

bubuko.com,布布扣
 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<queue>
 7 #include<vector>
 8 #include<map>
 9 #define MAXN 1000+5
10 #define MAXM 20000+5
11 #define oo 95565314
12 
13 using namespace std;
14 int cas,n,cash,kn;
15 
16 map<string,int>kinds;
17 int getK(string s)
18 {
19     if (kinds.count(s)) return kinds[s];
20     else return kinds[s]=kn++;
21 }
22 
23 struct Comp
24 {
25     int price,qual;//价格,品质因子,“名称”是无关因素
26     Comp(){}
27     Comp(int p,int q){price=p;qual=q;}
28 };
29 vector<Comp> comp[MAXN];//定义成一维线性广义表,每个元素是一个优先队列,保证价格从小到大排序
30 
31 bool isok(int x)//枚举最小的最大的品质因子,二分
32 {//统一思想是,在每类物品种,选择买品质因子至少为x,且价格最低的
33     int count=0;
34     for(int i=0;i<kn;i++)
35     {
36         int m=comp[i].size();
37         int aim=oo;//需要买的最低的价格
38         for(int j=0;j<m;j++)//遍历每种物品
39         {
40             if (comp[i][j].qual>=x) aim=min(aim,comp[i][j].price);
41         }
42         if (aim>=oo) return false;//可能品质过高,一件也无法购买
43         count+=aim;
44     }
45     if (count>cash) return false;else return true;
46 }
47 void init()
48 {
49     for(int i=0;i<n;i++) comp[i].clear();//清空队列
50     kinds.clear();
51     kn=0;
52 }
53 int main()
54 {
55     cin>>cas;
56     for(;cas;cas--)
57     {
58         cin>>n>>cash;
59 
60         init();//初始化
61         int maxq=0;//二分枚举的上限,即最大的品质因子
62         for(int i=0;i<n;i++)
63         {
64             char kname[100],name[100];
65             int p,q;
66             cin>>kname>>name>>p>>q;
67             int k=getK(kname);
68             maxq=max(maxq,q);
69             comp[k].push_back((Comp){p,q});
70         }
71         int l=0,r=maxq+1;//防止越界‘
72         while(l<r)
73         {
74             int m=(r+l+1)/2;//向上取整,不然可能一直取不到最优解
75             if (isok(m)) l=m;//品质因子至少是m
76             else r=m-1;
77         }
78         cout<<l<<endl;
79     }
80     return 0;
81 }
bubuko.com,布布扣

 

 

关键词:二分

拓展思考:如果这道题满足条件:每种配件中,品质因子越高,价格越高,则可以大大扩大n。原来的vector每个节点可以变成一个优先队列,排序方式是先按品质因子,再按价格,从小到大,最后二分找到第一个品质因子为x的物品就可以了,内层的复杂读不需要On)。

UVALive3971组装电脑

原文:http://www.cnblogs.com/little-w/p/3515814.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!