題目大意:
產品有n個部分 組成 每個部分有m種選擇,每個部件 有bandwith和price兩種屬性
求 一種選擇方案使B/P 最大 其中 B是各個部件bandwith的最小值 P是各個部件price的和
我的做法:
將bandwith排序,然后分別以每一個bandwith最為最小值時 求出可取方案中price值最小的 那個(即 使B/P最大)
然后綜合起來 求最大的B/P
下面是我的代碼:
雖然AC了,但是還是有一點疑惑,在某一minBand為最小值時,所取得方案中肯定包含一個產品選擇的bandwith = minBand,否則最小值不是minBand,但是我沒有做這個判斷
代碼如下,僅作參考:
1
#include <iostream>
2
#include <set>
3
#include <algorithm>
4
using namespace std;
5
6
struct Device
7
{
8
int nChoice;
9
int quality[102][2];
10
};
11
12
int main()
13
{
14
int ncase;
15
cin >> ncase;
16
while ( ncase-- ){
17
18
int n;
19
double ratio = 0;
20
set <int> intSet;
21
set <int>::iterator sp;
22
cin >> n;
23
Device *s = new Device[n];
24
25
for( int i = 0; i < n; i++ ) {
26
cin >> s[i].nChoice;
27
for( int j = 0; j < s[i].nChoice; j++ ){
28
cin >> s[i].quality[j][0] >> s[i].quality[j][1];
29
intSet.insert( s[i].quality[j][0] );
30
}
31
}
32
33
for( sp = intSet.begin(); sp != intSet.end(); sp++ ){
34
int totalPrice = 0;
35
int minBand = *sp;
36
for( int i = 0; i < n; i++){//選每一種產品
37
int min = 100000;
38
for( int j = 0; j < s[i].nChoice; j++ ){
39
if( s[i].quality[j][0] >= minBand && min > s[i].quality[j][1] )
40
min = s[i].quality[j][1];
41
}
42
totalPrice += min;
43
}
44
if( ratio < (double) (minBand) / (double) totalPrice ){
45
ratio = (double) (minBand) / (double) totalPrice;
46
}
47
}
48
printf( "%.3lf\n", ratio );
49
50
delete s;
51
}
52
system("pause");
53
return 0;
54
}
55

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

一開始,我寫的是min = s[i].quality[0][1];弄了好久都不知道哪里錯了,后來發現原來第一個不一定取,這個做每次都toalPrice都是一樣的....標出來,警示自己一下,呵呵 估計 大家都沒有錯的這么白癡的 >_<