UVALive3971组装电脑

2023-10-13 20:41:52

UVALive3971

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

题目描述：组装电脑

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

解题思路：

运筹三要素分析：

决策方案:

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

约束条件：

A：总价格不超过b元；

目标评判标准：

B：最小的品质因子最大；

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

算法分析：

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

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

代码分析：

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

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

全部代码：

 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 }

关键词：二分

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

UVALive3971组装电脑

码农公寓

相关文章