Simple greedy strategy

Greed and proof

Choose a greedy strategy , We must first prove that the greedy strategy is correct , To consider using . In many cases , The rationality of greed is not obvious , But if we can find a counterexample , It can be proved that such greed is not correct .

Part of the knapsack problem

Part of the knapsack problem
When items with knapsack problems can be cut arbitrarily , The greedy strategy is right . That makes sense . Just take the commodity with the highest unit value , Filling the bag is the optimal solution .
ac Code ：

#include <iostream>
#include <algorithm>
using namespace std;

int n, t;
const int N = 110;

struct Coin
{
    
	double v;
	double w;
	double val;
	bool operator<(const Coin& c) const
	{
    
		return val < c.val;
	}
}coin[N];

int main()
{
    
	cin >> n >> t;
	for(int i = 0; i < n; i++)
	{
    
		double w, v;
		cin >> w >> v;
		coin[i] = {
    v, w, v / w};
	} 
	sort(coin, coin + n);
	double ans = 0;
	for(int i = n - 1; i >= 0; i--)
	{
    
		if(t < coin[i].w)
		{
    
			ans += coin[i].val * t;
			t = 0;	
			break;
		} 
		else if(t > 0)
		{
    
			t -= coin[i].w;
			ans += coin[i].v;
		}
	}
	printf("%.2lf", ans);
}

But how to prove that when the backpack problem items can not be cut , The greedy strategy is wrong ？
You can use the counter evidence , As long as there is an example to prove that greed is wrong , Then it won't work .（ This example is easy to find , The test case given is a ）

Line up for water

Yes n People line up in front of a tap to get water , Suppose everyone gets water for Ti , Please program to find this n An order in which individuals line up , bring n The average waiting time of an individual is the smallest .

The problem is intuitively simple . Minimum average waiting time , It is to let the people who receive water for a long time wait , That is, the shorter the time of receiving water, the more people receive water first .

In fact, it's OK not to prove it , There are some examples , If there is no counterexample , It proves that greed is right . Violent enumeration can be used to verify the answer . If violence and greed agree , That greedy correctness is very high .

ac Code

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

struct P
{
    
	int id, t;
	bool operator< (const P& p) const
	{
    
		if(t == p.t) return id < p.id;
		else return t < p.t;
	}
}p[N];

int main()
{
    
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
    
		int t;
		cin >> t;
		p[i] = {
    i , t};
	}
	sort(p + 1, p + n + 1);
	double res = 0;
	int u = n;
	for(int i = 1; i <= n; i++)
	{
    
		res += p[i].t * (u - 1);
		u --;
		cout << p[i].id << ' ';
	}
	puts("");
	printf("%.2lf", res / n);
}

Messy yyy/ Line segments cover

Line segments cover
This is a classic greedy problem . It's a given n Intervals , At most several intervals are not coincident or intersecting .

Ideas ： From left to right , Find the leftmost end position . In this way, more space can be placed in the later section . In this step is the local optimal solution . Then continue to find the leftmost section , Put it if you can （ It is possible that the interval is more to the left , But there is overlap , Then you can't let it go ）.

In this way, each step is a local optimal solution , That is the global optimal solution .

So we just sort by end position in ascending order .

ac Code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

struct Contest
{
    
	int begin, end;
	bool operator< (const Contest& c) const
	{
    
		return end < c.end;
	}
}contest[N];

int main()
{
    
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
    
		int b, e;
		cin >> b >> e;
		contest[i] = {
    b , e};	
	}
	sort(contest, contest + n);
	
	int ans = 0, end = -1;
	for(int i = 0; i < n; i++)
		if(contest[i].begin >= end) 
		{
    
			ans++;
			end = contest[i].end;
		}
	cout << ans;
}