贪心算法（Fatmouse’Trade、今年暑假不AC）

Fatmouse’Trade

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <string>
 5 #include <stdio.h>
 6 #include <iomanip>
 7 using namespace std;
 8 /*
 9     题目：FatMouse'Trade
10     用时：tomato *
11     思路：贪心
12     坑：一直显示没有通过所有的测试用例
13     1. m设置为double，所有的float都设置成double %lf 类型即可 
14 */
15 
16 struct goods
17 {
18     double catFood;
19     double javabean;
20     double w ;
21     bool operator <(const goods & g)const{
22         return w-g.w > 0; // 降序排列
23     }
24 }buf[1000];
25 
26 
27 int main()
28 {
29     double m;
30     int n;
31     cin >> m >> n;
32     double result=0;
33     while (m!= -1 && n!= -1)
34     {
35         for (int i=0;i<n;i++)
36         {
37             cin>>buf[i].javabean >> buf[i].catFood;
38             buf[i].w = (float)buf[i].javabean/buf[i].catFood;
39         }
40         sort(buf,buf+n);
41         result =0;
42         for (int i=0;i<n && m > 0;i++)
43         {
44             if (buf[i].catFood <= m )
45             { // catFood足够充裕买完这个room所有的bean
46                 m = m - buf[i].catFood ;
47                 result += buf[i].javabean;
48             }
49             else{ // 猫粮不够充裕仅仅能买一部分
50                 result += buf[i].w * m;
51                 m = 0 ;
52             }
53         }
54         printf("%.3lf
",result);
55         cin >> m >>n;
56     }
57 
58     return 0;
59 }

今年暑假不AC

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N = 100;
 7 struct show
 8 {
 9     int start ;
10     int end1;
11     bool operator < (const show &a)const{
12     return end1 < a.end1 ;
13     }
14 };
15 
16 bool cmp(const show &a,const show &b)
17 {
18     return a.end1 <= b.end1 ;
19 }
20 
21 int main()
22 {
23    int n,i,j;
24    show show[N];
25    while (cin >> n && n!=0)
26    {
27    for (i=0;i<n;i++)
28    {
29     cin >> show[i].start >>show[i].end1 ;
30    }
31    sort(show,show+n,cmp);
32    int sum = 1;
33    for (i = 0 , j = 1;i < n && j < n; j++)
34    {
35     if (show[j].start >= show[i].end1)
36     {
37         sum ++;
38         i=j;
39     }
40    }
41    cout << sum << endl;
42    }
43     return 0;
44 }