贪心入门题

1.hdu 1009 FatMouse' Trade

题目传送门[戳我]

题解传送门[戳我]

2.删数问题

题目&评测传送门[戳我]

（PS）

题解:

　　通过贪心的策略来想，应该是每一次选择局部最优解。

　　这个局部最优解就是使当前的数最小，所以可以从高位到低位进行查找，使得s[j + 1] >= s[j]否则，删掉第j个数

Code

 1 /**
 2  * smartoj
 3  * Problem#1098
 4  * Accepted
 5  * Time:107ms
 6  * Memory:516k 
 7  */
 8 #include<iostream>
 9 #include<cstdio>
10 #include<cctype>
11 #include<cstring>
12 #include<cstdlib>
13 #include<cmath>
14 #include<fstream>
15 #include<sstream>
16 #include<algorithm>
17 #include<map>
18 #include<set>
19 #include<queue>
20 #include<vector>
21 #include<stack>
22 using namespace std;
23 typedef bool boolean;
24 #define INF 0xfffffff
25 #define smin(a, b) a = min(a, b)
26 #define smax(a, b) a = max(a, b)
27 template<typename T>
28 inline void readInteger(T& u){
29     char x;
30     int aFlag = 1;
31     while(!isdigit((x = getchar())) && x != '-');
32     if(x == '-'){
33         x = getchar();
34         aFlag = -1;
35     }
36     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
37     ungetc(x, stdin);
38     u *= aFlag;
39 }
40 
41 vector<char> str;
42 int s;
43 
44 inline void init(){
45     char x;
46     while((x = getchar()) != '
'){
47         str.push_back(x);
48     }
49     readInteger(s);
50 }
51 
52 inline void solve(){
53     for(int i = 1; i <= s; i++){
54         int j = 0;
55         while(j < (signed)str.size() - 1 && str[j + 1] >= str[j]){
56             j++;    
57         }
58         str.erase(str.begin() + j);
59     }
60     int i = 0;
61     while(i < str.size() && str[i] == '0') i++;
62     for(; i < str.size(); i++){
63         putchar(str[i]);
64     }
65 }
66 
67 int main(){
68     init();
69     solve();
70     return 0; 
71 }
删数问题

3.hdu 1045 Fire Net

题目传送门[戳我]

题解:

　　一个很神奇的方法AC，按如果在(x, y)这个地方建城堡造成的影响数排序，然后for循环一边，把能建的都建，然后输出结果。

Code

  1 /**
  2  * acm.hdu.com.cn
  3  * Problem#1045
  4  * Accepted
  5  * Time:15ms
  6  * Memory:1568k
  7  */
  8 #include<iostream>
  9 #include<cstdio>
 10 #include<cctype>
 11 #include<cstring>
 12 #include<cstdlib>
 13 #include<cmath>
 14 #include<fstream>
 15 #include<sstream>
 16 #include<algorithm>
 17 #include<map>
 18 #include<set>
 19 #include<queue>
 20 #include<vector>
 21 #include<stack>
 22 using namespace std;
 23 typedef bool boolean;
 24 #define INF 0xfffffff
 25 #define smin(a, b) a = min(a, b)
 26 #define smax(a, b) a = max(a, b)
 27 template<typename T>
 28 inline void readInteger(T& u){
 29     char x;
 30     int aFlag = 1;
 31     while(!isdigit((x = getchar())) && x != '-');
 32     if(x == '-'){
 33         x = getchar();
 34         aFlag = -1;
 35     }
 36     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
 37     ungetc(x, stdin);
 38     u *= aFlag;
 39 }
 40 
 41 int n;
 42 int f[5][5];
 43 
 44 inline boolean init(){
 45     readInteger(n);
 46     if(n == 0)    return false;
 47     for(int i = 1; i <= n; i++){
 48         getchar();
 49         for(int j = 1; j <= n; j++){
 50             char x = getchar();
 51             if(x == 'X')
 52                 f[i][j] = 1;
 53             else f[i][j] = 0;
 54         }
 55     }
 56     return true;
 57 }
 58 
 59 int roles[5][5];
 60 
 61 void fire(int x, int y){
 62     for(int i = x - 1; i >= 1 && f[i][y] == 0; i--){        roles[x][y]++;    }
 63     for(int i = x + 1; i <= n && f[i][y] == 0; i++){        roles[x][y]++;    }
 64     for(int j = y - 1; j >= 1 && f[x][j] == 0; j--){        roles[x][y]++;    }
 65     for(int j = y + 1; j <= n && f[x][j] == 0; j++){        roles[x][y]++;    }
 66 }
 67 
 68 typedef class Data{
 69     public:
 70         int x, y;
 71         int data;
 72         Data(const int x = 0, const int y = 0, const int data = 0):x(x), y(y), data(data){}
 73 }Data;
 74 
 75 boolean cmpare(const Data& a, const Data& b){
 76     return a.data < b.data;
 77 }
 78 
 79 vector<Data> l;
 80 boolean visited[5][5];
 81 inline void solve(){
 82     memset(roles, 1, sizeof(roles));
 83     memset(visited, false, sizeof(visited));
 84     for(int i = 1; i <= n; i++){
 85         for(int j = 1; j <= n; j++){
 86             if(f[i][j] == 0){
 87                 fire(i, j);
 88                 l.push_back(Data(i, j, roles[i][j]));
 89             }
 90         }
 91     }
 92     sort(l.begin(), l.end(), cmpare);
 93     int result = 0;
 94     for(int k = 0; k < (signed)l.size(); k++){
 95         if(!visited[l[k].x][l[k].y]){
 96             result++;
 97             int &x = l[k].x, &y= l[k].y;
 98             for(int i = x - 1; i >= 1 && f[i][y] == 0; i--){        visited[i][y] = true;    }
 99             for(int i = x + 1; i <= n && f[i][y] == 0; i++){        visited[i][y] = true;    }
100             for(int j = y - 1; j >= 1 && f[x][j] == 0; j--){        visited[x][j] = true;    }
101             for(int j = y + 1; j <= n && f[x][j] == 0; j++){        visited[x][j] = true;    }
102         }
103     }
104     l.clear();
105     printf("%d
", result);
106 }
107 
108 int main(){
109     while(init()){
110         solve();
111     }
112     return 0;
113 }
Fire Net

4.hdu 1050 Moving Table

题目传送门[戳我]

题解:

　　还是很神奇的方法，用差分，标记每次移动影响的范围，前缀和完了找出一个最大值乘10。因为不同地方可以同时进行，只有有地方重叠的时候需要分批扮桌子。

Code

 1 /**
 2  * acm.hdu.com.cn
 3  * Problem#1050
 4  * Accepted
 5  * Time:0ms
 6  * Memory:1552k
 7  */
 8 #include<iostream>
 9 #include<cstdio>
10 #include<cctype>
11 #include<cstring>
12 #include<cstdlib>
13 #include<fstream>
14 #include<sstream>
15 #include<algorithm>
16 #include<map>
17 #include<set>
18 #include<queue>
19 #include<vector>
20 #include<stack>
21 #include<cmath>
22 using namespace std;
23 typedef bool boolean;
24 #define INF 0xfffffff
25 #define smin(a, b) a = min(a, b)
26 #define smax(a, b) a = max(a, b)
27 template<typename T>
28 inline void readInteger(T& u){
29     char x;
30     int aFlag = 1;
31     while(!isdigit((x = getchar())) && x != '-');
32     if(x == '-'){
33         x = getchar();
34         aFlag = -1;
35     }
36     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
37     ungetc(x, stdin);
38     u *= aFlag;
39 }
40 
41 int T;
42 int n;
43 int used[205];
44 
45 inline void init(){
46     readInteger(n);
47     for(int i = 1, a, b, c, d; i <= n; i++){
48         readInteger(a);
49         readInteger(b);
50         c = (min(a, b) + 1) >> 1;
51         d = (max(a, b) + 1) >> 1;
52         used[c] += 1, used[d + 1] -= 1;
53     }
54 }
55 
56 inline void solve(){
57     int result = 0;
58     for(int i = 1; i <= 201; i++){
59         used[i] += used[i - 1];
60         smax(result, used[i]);
61     }
62     printf("%d
", result * 10);
63     memset(used, 0, sizeof(used));
64 }
65 
66 int main(){
67     readInteger(T);
68     while(T--){
69         init();
70         solve();
71     }
72     return 0;
73 }
Moving Table

5.hdu 1051 Wooden Sticks

题目传送门[here]

题解:

　　当成一个二元组排个序，然后每次往后找，保证每次找到的都不需要准备时间，每次循环完了将准备时间加1，前面最大的weight清0

Code

 1 /**
 2  * acm.hdu.com.cn
 3  * Problem#1051
 4  * Accepted
 5  * Time:15ms
 6  * Memory:1644k
 7  */
 8 #include<iostream>
 9 #include<cstdio>
10 #include<cctype>
11 #include<cstring>
12 #include<cstdlib>
13 #include<cmath>
14 #include<fstream>
15 #include<sstream>
16 #include<algorithm>
17 #include<map>
18 #include<set>
19 #include<queue>
20 #include<vector>
21 #include<stack>
22 using namespace std;
23 typedef bool boolean;
24 #define INF 0xfffffff
25 #define smin(a, b) a = min(a, b)
26 #define smax(a, b) a = max(a, b)
27 template<typename T>
28 inline void readInteger(T& u){
29     char x;
30     int aFlag = 1;
31     while(!isdigit((x = getchar())) && x != '-');
32     if(x == '-'){
33         x = getchar();
34         aFlag = -1;
35     }
36     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
37     ungetc(x, stdin);
38     u *= aFlag;
39 }
40 
41 typedef class Stick{
42     public:
43         int length;
44         int weight;
45         Stick(const int length = 0, const int weight = 0):length(length), weight(weight){    }
46         boolean operator <(Stick another) const {
47             if(this->length != another.length)    return this->length < another.length;
48             return this->weight < another.weight;
49         }
50 }Stick;
51 
52 int T;
53 int n;
54 Stick *ss;
55 
56 inline void init(){
57     readInteger(n);
58     ss = new Stick[(const int)(n + 1)];
59     for(int i = 1; i <= n; i++){
60         readInteger(ss[i].length);
61         readInteger(ss[i].weight);
62     }
63 }
64 
65 boolean *visited;
66 inline void solve(){
67     int finished = 0;
68     int result = 0, last;
69     sort(ss + 1, ss + n + 1);
70     visited = new boolean[(const int)(n + 1)];
71     memset(visited, false, sizeof(boolean) * (n + 1));
72     while(finished < n){
73         result++;
74         last = 0;
75         for(int i = 1; i <= n; i++){
76             if(!visited[i] && ss[i].weight >= last){
77                 finished++;
78                 visited[i] = true;
79                 last = ss[i].weight;
80             }
81         }
82     }
83     printf("%d", result);
84     delete[] ss;
85     delete[] visited;
86 }
87 
88 int main(){
89     readInteger(T);
90     while(T--){
91         init();
92         solve();
93         putchar('
');
94     }
95     return 0;
96 }
Wooden Stacks

6.UVa 10755 Garbage Heap

原题传送门[here]

VJudge传送门:[here]

题解:

　　首先降低维数，枚举x1, x2, y1, y2，然后可以将这一段压缩成一维的一段。然后就可以贪心了，为了让z1 - z2这一段竟可能大，所以应该使s[z2] - s[z1 - 1]尽可能小。然后加个前缀和降低时间复杂度，就可以开开心心地交vjudge了

  1 /**
  2  * uva
  3  * Problem#10755
  4  * Accepted
  5  * Time:180ms
  6  */
  7 #include<iostream>
  8 #include<cstdio>
  9 #include<cctype>
 10 #include<cstring>
 11 #include<cstdlib>
 12 #include<cmath>
 13 #include<fstream>
 14 #include<sstream>
 15 #include<algorithm>
 16 #include<map>
 17 #include<set>
 18 #include<queue>
 19 #include<vector>
 20 #include<stack>
 21 using namespace std;
 22 typedef bool boolean;
 23 #define INF 0xfffffff
 24 #define smin(a, b) a = min(a, b)
 25 #define smax(a, b) a = max(a, b)
 26 template<typename T>
 27 inline void readInteger(T& u){
 28     char x;
 29     int aFlag = 1;
 30     while(!isdigit((x = getchar())) && x != '-');
 31     if(x == '-'){
 32         x = getchar();
 33         aFlag = -1;
 34     }
 35     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
 36     ungetc(x, stdin);
 37     u *= aFlag;
 38 }
 39 
 40 const long long inf = (1LL << 60);
 41 
 42 template<typename T>
 43 inline void putInteger(T u){
 44     if(u == 0){
 45         putchar('0');
 46         return;
 47     }
 48     if(u < 0){
 49         putchar('-');
 50         u *= -1;
 51     }
 52     stack<char>    s;
 53     while(u != 0)    s.push(u % 10 + '0'), u /= 10;
 54     while(!s.empty())    putchar(s.top()), s.pop();
 55 }
 56 
 57 void expand(int i, int& x, int& y, int& z, int& sign){    //容斥原理 
 58     x = i & 1, i >>= 1;
 59     y = i & 1, i >>= 1;
 60     z = i & 1;
 61     sign = ((x + y + z) % 2 == 1) ? (1) : (-1);
 62 }
 63 
 64 int T;
 65 int a, b, c;
 66 
 67 long long s[21][21][21];
 68 inline void init_sum(){
 69     for(int i = 1; i <= a; i++){
 70         for(int j = 1; j <= b; j++){
 71             for(int k = 1; k <= c; k++){
 72                 for(int p = 1; p < 8; p++){
 73                     int x, y, z, sign;
 74                     expand(p, x, y, z, sign);
 75                     s[i][j][k] += s[i - x][j - y][k - z] * sign;
 76                 }
 77             }
 78         }
 79     }
 80 }
 81 
 82 //long long f[21];
 83 inline long long dp(int x1, int x2, int y1, int y2){
 84     long long sumz;
 85     long long result = -inf;
 86     long long minv = 0;
 87     int dx = x2 - x1 + 1, dy = y2 - y1 + 1;
 88     for(int i = 1; i <= c; i++){
 89         sumz = s[x2][y2][i];
 90         for(int p = 1; p < 8; p++){
 91             int x, y, z, sign;
 92             expand(p, x, y, z, sign);
 93             //sumz -= s[x2 - x * dx][y2 - y * dy][i - z] * sign;
 94             sumz -= s[x2 - x * dx][y2 - y * dy][i - z * i] * sign;
 95         }
 96         smax(result , sumz - minv);
 97         smin(minv, sumz);
 98 //        f[i] = max(0LL, f[i - 1]) + sumz;
 99 //        smax(result, f[i]);
100     }
101     return result;
102 }
103 
104 inline void init(){
105     readInteger(a);
106     readInteger(b);
107     readInteger(c);
108     memset(s, 0, sizeof(s));
109     for(int i = 1; i <= a; i++){
110         for(int j = 1; j <= b; j++){
111             for(int k = 1; k <= c; k++){
112                 readInteger(s[i][j][k]);
113             }
114         }
115     }
116 }
117 
118 inline void solve(){
119     long long result = -inf;
120     for(int x1 = 1; x1 <= a; x1++){
121         for(int x2 = x1; x2 <= a; x2++){
122             for(int y1 = 1; y1 <= b; y1++){
123                 for(int y2 = y1; y2 <= b; y2++){
124                     long long cmp = dp(x1, x2, y1, y2);
125                     smax(result, cmp);
126                 }
127             }
128         }
129     }
130     putInteger(result);
131     putchar('
');
132 }
133 
134 int main(){
135     readInteger(T);
136     while(T--){
137         init();
138         init_sum();
139         solve();
140         if(T)    putchar('
');
141     }
142     return 0;
143 }
Garbage Heap

7.USACO 1.3 Mixing Milk

原题传送门[here]

题目大意:

　　一个公司需要购买N个单位的牛奶，有M个农民每天提供定价定量的牛奶。第i个农民的牛奶每个单位售价为Pi，每天提供Ai个单位的牛奶。求每天最小的开销。

题解:

　　和第一道题有些相似，按照单价排序，然后计算结果就行了。

 1 /*
 2 ID: m1582851
 3 PROG: milk
 4 LANG: C++11
 5 */
 6 /**
 7  * USACO
 8  * Accepted
 9  * Time:0ms
10  * Memory:4184k
11  */
12 #include<iostream>
13 #include<cstdio>
14 #include<cctype>
15 #include<cstring>
16 #include<cstdlib>
17 #include<fstream>
18 #include<sstream>
19 #include<algorithm>
20 #include<map>
21 #include<set>
22 #include<queue>
23 #include<vector>
24 #include<stack>
25 using namespace std;
26 typedef bool boolean;
27 #define INF 0xfffffff
28 #define smin(a, b) a = min(a, b)
29 #define smax(a, b) a = max(a, b)
30 template<typename T>
31 inline void readInteger(T& u){
32     char x;
33     int aFlag = 1;
34     while(!isdigit((x = getchar())) && x != '-');
35     if(x == '-'){
36         x = getchar();
37         aFlag = -1;
38     }
39     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
40     ungetc(x, stdin);
41     u *= aFlag;
42 }
43 
44 typedef class Milk{
45     public:
46         int weight;
47         int cost;
48         Milk(const int weight = 0, const int cost = 0):weight(weight), cost(cost){    }
49         boolean operator < (Milk another) const {
50             return this->cost < another.cost;
51         }
52 }Milk;
53 
54 int n, m;
55 Milk* milks;
56 int result = 0;
57 
58 inline void init(){
59     readInteger(n);
60     readInteger(m);
61     milks = new Milk[(const int)(m + 1)];
62     for(int i = 1; i <= m; i++){
63         readInteger(milks[i].cost);
64         readInteger(milks[i].weight);
65     }
66 }
67 
68 inline void solve(){
69     sort(milks + 1, milks + m + 1);
70     for(int i = 1; i <= m && n; i++){
71         int maxcer = min(n, milks[i].weight);
72         result += maxcer * milks[i].cost;
73         n -= maxcer;
74     }
75     printf("%d
", result);
76 }
77 
78 int main(){
79     freopen("milk.in", "r", stdin);
80     freopen("milk.out", "w", stdout);
81     init();
82     solve();
83     return 0;
84 }
Mixing Milk

8.USACO 1.3 Barn Repair

原题传送门[here]

题目大意:

　　用长度任意，数量不超过M的木板挡住有牛的牛棚（每个牛棚的长度都看作1， 一共有C个牛棚有牛，并且给出每只牛在哪个牛棚里）的出路（必须堵住所有牛棚的出口），求最小的木板的长度的和

题解:

　　首先把一段一段的连续有牛的牛棚之间的间隔的长度求出来，计算的方法是后一个的起始位置减去前一个的结束位置减1。只需要连接间隔较小的几段，所以就从小到大排序。需要连接的次数是 总空缺数减去M然后加1。接着把最小的几个加起来然后加上C就完成了。

 1 /*
 2 ID: m1582851
 3 PROG: barn1
 4 LANG: C++11
 5 */
 6 /**
 7  * USACO
 8  * Accepted
 9  * Time:0ms
10  * Memory:4184k
11  */
12 #include<iostream>
13 #include<cstdio>
14 #include<cctype>
15 #include<cstring>
16 #include<cstdlib>
17 #include<fstream>
18 #include<sstream>
19 #include<algorithm>
20 #include<map>
21 #include<set>
22 #include<queue>
23 #include<vector>
24 #include<stack>
25 using namespace std;
26 typedef bool boolean;
27 #define INF 0xfffffff
28 #define smin(a, b) a = min(a, b)
29 #define smax(a, b) a = max(a, b)
30 template<typename T>
31 inline void readInteger(T& u){
32     char x;
33     int aFlag = 1;
34     while(!isdigit((x = getchar())) && x != '-');
35     if(x == '-'){
36         x = getchar();
37         aFlag = -1;
38     }
39     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
40     ungetc(x, stdin);
41     u *= aFlag;
42 }
43 
44 int m, s, c;
45 vector<int> jgs;
46 int* stalls;
47 int result;
48 
49 inline void init(){
50     readInteger(m);
51     readInteger(s);
52     readInteger(c);
53     stalls = new int[(const int)(c + 1)];
54     for(int i = 1; i <= c; i++){
55         readInteger(stalls[i]);
56     }
57 }
58 
59 inline void solve(){
60     sort(stalls + 1, stalls + c + 1);
61     for(int i = 2; i <= c; i++){
62         if(stalls[i] > stalls[i - 1] + 1)
63             jgs.push_back(stalls[i] - stalls[i - 1] - 1);
64     }
65     sort(jgs.begin(), jgs.end());
66     int needed = (signed)jgs.size() - m;
67     result = c;
68     for(int i = 0; i <= needed; i++){
69         result += jgs[i];
70     }
71     printf("%d
", result);
72 }
73 
74 int main(){
75     freopen("barn1.in", "r", stdin);
76     freopen("barn1.out", "w", stdout);
77     init();
78     solve();
79     return 0;
80 }
Barn Repair
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yyf0309/p/6071526.html