发表于 | | 次阅读

@TOC

贪心算法

胖耗子的交易

题目描述：
  FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
输入：
  The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
输出：
  For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
样例输入：
    5 3
    7 2
    4 3
    5 2
    20 3
    25 18
    24 15
    15 10
    -1 -1
样例输出：
    13.333
    31.500

简单说来就是：m元钱，n中物品，每种物品j磅，总价值f元。

解题思路：每一次购买的时候先购买性价比最高的物品，再接着购买性价比较低的物品，一直以这个思路购买。

C++实现算法：

1
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
#include <iostream>
#include <algorithm>
using namespace std;

struct JavaBean {
    double jbean;    //  物品的总质量
    double fcat;     //  物品的总价格
    double per;      //  物品的性价比 
    bool operator < (const JavaBean &jb) const {
    	//  重载小于运算符，确保可以使用sort函数将数组按照降序排列 
        return per > jb.per;
    }
} buff[1001];

int main() {
    double m;
	int n;
    while(scanf("%lf%d", &m, &n) != EOF) {
        if (m == -1 || n == -1)
            break;
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &buff[i].jbean, &buff[i].fcat);
            buff[i].per = buff[i].jbean / buff[i].fcat;
        }

        sort(buff, buff + n);
	
        double money = m;
        int i = 0;
        double max = 0;
        for (int i = 0; i < n; i++) {
            if (money > 0) {
                if (money > buff[i].fcat) {
                    money -= buff[i].fcat;
                    max += buff[i].jbean;
                } else {
                    max += buff[i].per * money;
                    money = 0;
                }
            } else {
                break;
            }
        }

        printf("%.3lf\n", max);
    }
    return 0;
}

今年暑假不AC

题目描述：输入数据包含多个测试实例，每个测试实例的第一行只有一个整树n(0 < n <= 100), 表示你喜欢看的节目总数，然后是n行数据，有两个整数ts和te分别表示节目的开始时间和结束时间，你如何安排时间表才能尽可能多的看完节目。
样例输入：
    12
    1 3
    3 4
    0 7
    3 8
    15 19
    15 20
    10 15
    8 18
    6 12
    5 10
    4 14
    2 9
    0
样例输出：
    5

解析：第一个选择的节目一定是结束时间最早的节目，那么第一个选定后，第二个的选择同样是相同的道理。

C++实现程序：

1
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
#include <iostream>
#include <algorithm>
using namespace std;

struct Time {
    int start;
    int end;
    bool operator < (const Time &T) const {
        return end < T.end;
    }
} buff[101];

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        for (int i = 0; i < n; i++)
            scanf("%d%d", &buff[i].start, &buff[i].end);

        sort(buff, buff + n);
		
        int earend = 0;
        int num = 1;
        for (int i = 1; i < n; i++) {
            if (buff[i].start >= buff[earend].end) {
                num++;
                earend = i;
            } else if (buff[i].start >= buff[earend].start 
                        && buff[i].end < buff[earend].end) {
                earend = i;
            }
        }

        printf("%d\n", num);
    }
    return 0;
}