1. What is greed and repentance
Repent greed means "repent" in the process of ordinary greed, thus turning some questions that seem to be not very greedy into greed and can be done by greed.
2. The common process of repentance and greed
It is to first use a well-thinked greed strategy and use the priority queue for maintenance. Then if you find that something cannot be selected when you are greedy, then you have to consider whether there is something worse than the thing you selected before. If there is one, throw away the worse thing you selected before and stuff this better thing into the priority queue. This is "repentance".
3. Repentance and greed framework
priority_queue<int>q;//The default is to be a large root heap, but sometimes a small root heap is needed
Begin greedy
{
if (this thing can be selected)
{
(This thing);
//Increase the count, some questions may also require adding other things.
}
else if(()&&The worst thing in the queue is worse than this one)
{
//Increase the count, some questions may also require adding other things.
();//Take away the bad ones
(This thing);// Throw it in
}
}Note: This is just a board, please adapt to the situation when applying.
4. Explanation of the greed example
CF1974G Money Buys Less Happiness Now
Repentance to Greedy Template Question. First of all, if you can increase the happiness value, increase the happiness value. If you can't increase (no money), then look at which months you obtained the happiness value before and find the most expensive month. If the price of that month is higher than the price of this month, throw away that month and join this month (because this will make more money and will not affect the happiness value).
Code:
#include<bits/stdc++.h>
using namespace std;
signed main()
{
int _;
scanf("%d",&_);
while(_--)
{
priority_queue<int>q;
int n,m,sum = 0,num = 0;
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++,sum+=m)
{
int x;
scanf("%d",&x);
if(x<=sum)
{
sum-=x;
num++;
(x);
}
else if(()&&()>x)
{
sum+=()-x;
();
(x);
}
}
printf("%d\n",num);
}
return 0;
}
CF1526C2 Potions (Hard Version)
First, if read in\(x \ge 0\), that's definitely the choice, because it won't have any negative effects on the answer, and then if\(sum+x \ge 0\), although\(sum\)(Currently, the prefix and) have become smaller, but it still does not affect it, so you can choose directly, but you have to add the priority queue here (because the previous one is greater than or equal to\(0\)The number of the number will not have any impact on the inability to select later. There is no need to join the priority queue, because if it cannot be selected later, it will definitely be a negative number, and the negative number cannot be greater than or equal to\(0\)) and then if\(sum+x<0\), it just cannot be selected, so let’s see if the worst negative number selected earlier is worse than this. If it is worse than this, “repent”.
Code:
#include<bits/stdc++.h>
using namespace std;
signed main()
{
int n;
long long sum = 0;
int num = 0;
scanf("%d",&n);
priority_queue<int,vector<int>,greater<int>>q;
for(int i = 1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(x>=0)
{
sum+=x;
num++;
}
else if(sum+x>=0)
{
sum+=x;
num++;
(x);
}
else
{
if(()&&()<x)
{
sum+=();
();
(x);
}
}
}
printf("%d",num);
return 0;
}
CF1185C2 Exam in BerSU (hard version)
The same routine is still the same. If you can choose, choose. If you can't choose, we will regret it.
If the output of this question cannot be selected, we must prepare a priority queue, because if we cannot choose, we must take out the largest (most dragging) from the priority queue every time, put it in this temporary priority queue, and then put it back after the output is completed. Then, when the output cannot be selected, it must be reduced.\(1\), because you haven't put this thing in the priority queue at that time (you can also put it first, so there is no need to reduce it\(1\)).
Code:
#include<bits/stdc++.h>
using namespace std;
signed main()
{
priority_queue<int>q,tmp;
int n,m,sum = 0;
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(sum+x<=m)
{
sum+=x;
(x);
printf("%d ",());
}
else
{
while(sum+x>m)
{
sum-=();
(());
();
}
printf("%d ",()-1);
while(())
{
sum+=();
(());
();
}
if(()>x)
{
sum-=()-x;
();
(x);
}
}
}
return 0;
}
P2949 [USACO09OPEN] Work Scheduling G
The same routine. First, you have to sort these tasks in chronological order, and then start to be greedy. If you still choose, choose what you can. If you can't choose, find the worst in the priority queue to see if there is any worse than the current one. If there is, put it in.
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
struct node
{
int d;
int p;
}a[N];
int cmp(node x,node y)
{
return <;
}
signed main()
{
priority_queue<int,vector<int>,greater<int>>q;
int num = 0,sum = 0;
int n;
scanf("%lld",&n);
for(int i = 1;i<=n;i++)
{
scanf("%lld %lld",&a[i].d,&a[i].p);
}
sort(a+1,a+n+1,cmp);
for(int i = 1;i<=n;i++)
{
if(num<a[i].d)
{
num++;
(a[i].p);
sum+=a[i].p;
}
else if(()<a[i].p)
{
sum+=a[i].();
();
(a[i].p);
}
}
printf("%lld",sum);
return 0;
}
CF865D Buy Low Sell High
Since there is only one stock, we are not sure when to buy a stock if we buy it. We can choose greedily. If the cheapest stock in the current priority queue is cheaper than the current stock price, then "sell" the stock (this is definitely correct, because even if we sell it later, the difference in profits is higher, the price we sold before will be placed in the priority queue. In theory, we sold that stock, but in fact, it can not only be the final result, but also serve as a repeater, so we can also trade with the subsequent stocks, and the answer will not be a problem). Then, no matter what, we have to put the current stock into the priority queue, because it still has a chance to be a repeater.
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
priority_queue<int,vector<int>,greater<int>>q;
int n,sum = 0;
scanf("%lld",&n);
for(int i = 1;i<=n;i++)
{
int x;
scanf("%lld",&x);
if(()&&()<x)
{
sum+=();
();
(x);
}
(x);
}
printf("%lld",sum);
return 0;
}
More examples will be updated later, so stay tuned! !
5. What is local adjustment method
The local adjustment method is to pick two adjacent positions when doing selective greed to analyze inequality in mathematics, thereby obtaining the sorting rules. At the same time, it also has an important purpose - to judge whether selective questions can be greedy.
6. General derivation process of local adjustment method
It is to define two adjacent numbers first\(x,y\), then assume that the number of other positions is fixed, and\(x,y\)It can be interchanged, so let's write it separately\(1,2,\dots,x,y,\dots,n-1,n\)Contributions and\(1,2,\dots,y,x,\dots,n-1,n\)Contributions, then assuming\(1,2,\dots,x,y,\dots,n-1,n\)Contribution ratio\(1,2,\dots,y,x,\dots,n-1,n\)The contribution is better, and then this is the sorting rule. Of course, sometimes this sorting rule is more troublesome, you can simplify it. So how can local adjustment be used to quickly determine whether selective questions can be greedy? It's very simple. You just need to judge whether our simplified inequality satisfies the partial order relationship. The partial order relationship means that you use small ones to connect the big ones to form a loop.Of course, partial order relationships also have a purely mathematical definition。
7. How to quickly determine whether an inequality that is not easy to judge satisfies partial order relationships
- Manually create data, and then write the sorting method according to this inequality. If it can be sorted out, it will satisfy the partial order relationship. If it cannot be taken, it will not satisfy the partial order relationship (
Note that this method is more important than Tang）。 - Directly use the three properties of partial order relationships to verify. If all are satisfied, there will be no problem. If not satisfied, there will be problems (
Note: This method is also relatively Tang）。
Although neither method must be guaranteed to be correct, the accuracy rate of putting together is definitely higher than 99%, and this is also a very useful method in algorithm competitions. Of course, you don’t need to put it together at all when applying it, just use one method casually.
7. Explanation of the local adjustment law
P1012 [NOIP 1998 Improve Group] Score
First write down the contributions of both to form an inequality (here\(A\)express\(x\)The result of the previous numbers being put together,\(B\)express\(x,y\)The result of the numbers behind it being put together):
Then let\(|DFG|\)express\(D\)and\(F\)and\(G\)The result of the combination is:
Then sort this sorting rule.
As for\(a_x \times 10^{|a_y|}+a_y>a_y \times 10^{|a_x|}+a_x\)Why is it partial order?
I found that it was all\(x\), on the other side are all\(y\), so it must be partial order.
Code:
#include <bits/stdc++.h>
using namespace std;
string a[25];
string ans;
bool cmp(string a,string b)
{
string c = a+b,d = b+a;
return c>d;
}
int main()
{
int n;
cin >> n;
for(int i = 1;i<=n;i++)
{
cin >> a[i];
}
sort(a+1,a+n+1,cmp);
for(int i = 1;i<=n;i++)
{
ans+=a[i];
}
cout << ans;
return 0;
}
P5963 [BalticOI ?] Card Card Game [Source Request]
First write down the contributions of both and form an inequality (assuming there are two sets of cards\((x_i,y_i),(x_j,y_j)\)）：
Isn't this done directly? And it's all on one side\(j\), on one side it's all\(i\)Therefore, it must be partial order.
Note: Ten years of OI is empty, and long long meets our ancestors.
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 6e5+5;
struct node
{
int x;
int y;
int sum;
}a[N];
int cmp(node x,node y)
{
return <;
}
signed main()
{
int n;
scanf("%lld",&n);
for(int i = 1;i<=n;i++)
{
scanf("%lld %lld",&a[i].x,&a[i].y);
a[i].sum = a[i].x+a[i].y;
}
sort(a+1,a+n+1,cmp);
int ans = 0;
for(int i = 1;i<=n/2;i++)
{
ans+=min(a[i].x,a[i].y);
}
for(int i = n/2+1;i<=n;i++)
{
ans-=max(a[i].x,a[i].y);
}
printf("%lld",ans);
return 0;
}