Review greed this week. As we all know, greed is that as long as you have the courage, you will find that, hey, you're overtime again
Therefore, I think the most important thing to pay attention to this kind of problem of greed is two points. One is what we are greedy for, that is, what the problem wants us to do; The other is how to optimize their greedy strategy, that is, pruning.
Of course, greed can be said to be an easy way to think of, and the problem is often not so friendly. Therefore, when you can't pass the problem with greed, it may be a better choice to find another way.
OK, family members, first of all, the first question is still operational. I'll be stunned when I come up. 01 backpack, ah, isn't this a problem in dynamic programming?
[Shenji 12. Example 1] some knapsack problems - Luogu
Here is a good time to recall the topic of backpack type. If there is a topic of officially starting to brush dynamic planning, I will explain it in detail.
Knapsack problem is mainly divided into 01 knapsack problem, complete knapsack problem and mixed knapsack problem.
This is obviously a 01 backpack, which only holds things in one state.
It's natural to solve the problem according to the board~
The first step is to understand the most important steps: 1. dp[i][j] indicates that the backpack has the maximum value when the weight of the backpack is j
2. For every kind of goods, there are two states of wearing and not wearing, which is naturally true
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) / / not installed and installed
Oh, by the way, remember to initially set dp[0][0~W] to 0, which means that when the first 0 items (i.e. none) are loaded into the backpack, the value of dp is 0
Then start the table and output the corresponding value after it is finished~
Well... I finished the wool. I found that it was... Not a backpack problem at all!
Convinced myself, pay attention to the topic "gold coins can be divided arbitrarily", so there is no problem that they can't fit at all
Therefore, we only need to sort their unit value to find the maximum value
This is actually a water problem
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
using namespace std;
struct Node{
double w,v,k;
}t[500];
bool cmp(Node a, Node b) {
return a.k > b.k;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> t[i].w >> t[i].v;
t[i].k = t[i].v / t[i].w;
}
sort(t + 1, t + 1 + n, cmp);
double sum = 0;
for (int i = 1; i <= n; i++) {
if (m >= t[i].w) {
sum = sum + t[i].v;
m = m - t[i].w;
}
else {
sum = sum + t[i].k * m;
break;
}
}
printf("%.2f", sum);
return 0;
}It's really greedy... Hehe TAT
Then there are some sorting problems that can be done with sort. There's nothing to say about this.
Oh, remember some motifs
Cluttered yyy / line segment coverage - Luogu
To get the most line segments, the most important thinking is to turn the right endpoints of these line segments from left to right, so that the line segments that can be put in form the most number of line segments
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
using namespace std;
const int mymax = 1e6 + 5;
struct Node {
int l, r;
}a[mymax];
bool cmp(Node a, Node b) {
return a.r < b.r;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].l >> a[i].r;
}
sort(a + 1, a + 1 + n, cmp);
int sum = 0;
int t = -1;
for (int i = 1; i <= n; i++) {
if (t <= a[i].l) {
t = a[i].r;
sum++;
}
}
cout << sum;
return 0;
}Then there was a that made me realize that my priority queue had forgotten a clean topic
[NOIP2004 improvement group] combined fruit / [USACO06NOV] Fence Repair G - Luogu
The meaning of this question is actually very simple. It means that you can pick out the smallest fruit pile each time, put it together, and then put it into all fruit piles until there is only one fruit pile left. All queues to be maintained are always from small to large or from large to small. Naturally, it comes to mind that priority queues should be used here~
Then you can see the posts of other leaders about the use of priority queue here. I won't say more here to avoid misleading you~
Finally, the AC code is issued for your reference
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>>p;
int main() {
int n;
cin >> n;
int t;
while (n--) {
cin >> t;
p.push(t);
}
int sum = 0;
while (p.size() != 1) {
int b = p.top();
p.pop();
int a = p.top();
p.pop();
sum = sum + a + b;
p.push(a + b);
}
cout << sum;
return 0;
}Then, it was an entry-level greedy problem, and it was specially judged to pit a wave of TAT
The analysis steps are as follows: observe the problem, 1. Repeat the operation; 2. There are traces to follow; 3. Large can be reduced to small
Eating sugar is a repeated operation, and the problem is the same. The process of processing n boxes of sugar is actually a repeated process of processing 3 boxes of sugar, so we can deduce that this problem can be solved by greedy method
Then, pay attention to the special judgment!
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
using namespace std;
const int mymax = 1e8 + 5;
long long a[mymax];
int main() {
int n,m;
cin >> n>>m;
long long sum = 0;
cin >> a[1];
if (a[1] > m) {
sum = sum + a[1] - m;
a[1] = m;
}
for (int i = 2; i <= n; i++) {
cin >> a[i];
if (a[i] + a[i - 1] > m) {
sum = sum+a[i] + a[i - 1] - m;
a[i] = m - a[i - 1];
}
}
cout << sum;
return 0;
}Let's move on. There are some very simple greedy problems. There's a pit filling problem that's quite interesting. Let's record it here
[NOIP2018 improvement group] road laying - Luogu
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<string>
using namespace std;
int a[1000000];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int sum = 0;
for (int i = 2; i <= n; i++) {
//A very important step is that the optimal scheme of multiple pits is actually the optimal scheme of multiple two pits
if (a[i] > a[i - 1]) {//The pit on the right is larger than the pit on the left, so the pit on the left is filled automatically
sum = sum + a[i] - a[i - 1];//Fill in the part that needs to be filled in
}
//If the pit on the right is smaller than the pit on the left, the pit has been treated in the previous scheme, so no additional treatment is required
}
sum = sum + a[1];
cout << sum;
return 0;
}
Then I got stuck with one of my questions
At that time, the first reaction was dp search, and then he did write a code that only got 10 points, which was harmful
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<string>
using namespace std;
const int mymax = 500;
long long a[mymax],p[mymax];
long long sum = -1;
int n, m;
void dp(int i, int k,int ans) {
if (k == n) {
if (ans >= sum) {
sum = ans;
}
return;
}
else {
p[i] = 1;
for (int j = 1; j <= n; j++) {
if (p[j] != 1) {
p[j] = 1;
dp(j, k + 1, ans + (a[i] - a[j]) * (a[i] - a[j]));
p[j] = 0;
}
}
p[i] = 0;
}
return;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i < n; i++) {
dp(i, 1,a[i]*a[i]);
}
cout << sum;
return 0;
}It is found that this method has to be optimized and can not be solved by finding the maximum path through all paths.
Then I thought, oh, my God, find the biggest gap, that is, jump from the smallest to the largest and then from the largest to the smallest every time?
Then... I found that this question is good water
The AC code is as follows:
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<string>
using namespace std;
const int mymax = 500;
long long a[mymax],p[mymax];
long long sum = 0;
int n, m;
int main() {
cin >> n;
a[0] = 0;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a , a + 1 + n);
int l = 0, r = n;
int k = 1;
while (l <= r) {
if (k == 1) {
sum = sum + (a[r] - a[l]) * (a[r] - a[l]);
l++;
k = 2;
}
else if (k == 2) {
sum = sum + (a[r] - a[l]) * (a[r] - a[l]);
r--;
k = 1;
}
}
cout << sum;
return 0;
}Then I think the greedy problem is a very important problem, that is, the problem will enable you to realize another additional condition when certain conditions are met
The last two questions in the list are of this type
[AHOI2018 junior high school group] grouping - Luogu
Like this question, you should make the group with the least number of people the largest while meeting the grouping requirements.
The difficulty of this problem is still very high. When I first thought of the greedy method, I first went from small to large rows. Once the difference is not 1, it will be output, so as to ensure the minimum length. Then I found that the last few checkpoints reported errors. I learned the ideas of everyone. It seems that this problem can be stored in the stack for optimization.
AC Code:
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<string>
using namespace std;
long long t[100005], n;
const int mymax = 100005;
int mymin = 99999999;
stack<int>q[mymax];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> t[i];
}
sort(t + 1, t + n + 1);
int p = 0;
int k = 0;//k indicates how many stacks there are currently
for (int i = 1; i <= n; i++) {
for (int j = k; j >= 1; j--) {
if (q[j].top() + 1 == t[i]) {
q[j].push(t[i]);
p = 1;
break;
}
p = 0;
}
if (p == 0) {
k++;
q[k].push(t[i]);
}
}
for (int i = 1; i <= k; i++) {
if (mymin >= q[i].size())mymin = q[i].size();
}
cout << mymin;
return 0;
}I'm confused. I feel the same as array thinking, but the last few test points passed.
Then there is the classic title: the king game
[NOIP2012 improvement group] king game - Luogu
This question is also a difficult one to think about. First of all, we should understand the meaning of the question. The gold coin that the nth person in the line can get is the product of the number on everyone's left hand divided by the number on this person's right hand. The title requires that the number of gold coins that can be obtained by these n individuals should be as small as possible.
The first is to simplify the process of repeated complex problems. This problem needs to line up n people. In fact, it is to line up two people for many times. Then take two people for analysis, and the goal is to make as few gold coins as possible.
After clarifying the above points and analyzing further, it can be concluded that when A1 * B1 > A2 * b2, b2 is in the front, so it can be concluded that when everyone is arranged in the order of ai*bi from small to large, the answers required for the questions can be obtained.
Then attach my 60 point code. This problem needs high precision to get the full score TAT
#include<iostream>
#include<stdio.h>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<string>
using namespace std;
struct Node {
int a, b;
}p[10005];
int n;
bool cmp(Node t1, Node t2) {
return t1.a * t1.b < t2.a* t2.b;
}
int main() {
cin >> n;
cin >> p[0].a >> p[0].b;
for (int i = 1; i <= n; i++)
{
cin >> p[i].a >> p[i].b;
}
sort(p + 1, p + 1 + n, cmp);
long long mymax = -1;
long long temp = p[0].a;
int t;
for (int i = 1; i <= n; i++) {
t = temp / p[i].b;
temp = temp * p[i].a;
if (mymax < t)mymax = t;
}
cout << mymax;
return 0;
}So far, the list of questions has been completed~
To sum up, there are no skills for the problem of greed. The main thing is whether you can find that the problem you do is greed
That is, a lot of repetitive work, clear requirements and simplified steps (personal view)
Well, see you next time~