The greedy problem in detail (c++)

catalogs

What is greed?

Example of greed

The problem of queuing for water

Solving for the number of systems to intercept missiles

What is greed?

greedy algorithm(also known as the greedy algorithm) is that theWhen solving a problem, always make the choice that seems best at the moment.. That is, without considering the overall optimality, he makes a solution that is in some sense locally optimal. The greedy algorithm does not yield an overall optimal solution for all problems, the key is toThe choice of greedy strategies, the greedy strategy chosen must have no posteriority, i.e., processes prior to a state do not affect later states and are only relevant to the current state. A prerequisite for the use of the greedy algorithm: a locally optimal solution must lead to a globally optimal solution

Example of greed

The problem of queuing for water

Title Description

There are n people lined up to fetch water from r taps, and the time they take to fill their buckets t1,t2,... ,tn are integers and each is unequal, how should their order of fetching water be arranged to minimize the total time they spend?

The time for each person to fetch water = the time of queuing + the actual time to fetch water, this question assumes that a person to fetch water, the person behind him then fetch water of this switching process does not consume time.

For example, there are 2 people, A and B, who take 3 and 2 minutes to fetch water, and there is only 1 tap. In this case, if A fetches water first, and B fetches water later, then the time taken by A and B to fetch water will be 3 and 3+2 respectively (B queues up for 3 minutes).

Thus, the total time for everyone to fetch water is the sum of the time for each person to fetch water and the time for each person to wait in line.

importation

On line 1, two integers n(1<=n<=500) and r(1<=r<=100).
On line 2, n positive integers t1,t2,... ,tn, (1<=ti<=1000) denote the time it took each person to fill the bucket.

exports

1 row, a positive integer indicating the minimum total time they spent.

example

importation

exports




#include <bits/stdc++.h>





using namespace std;



 



int n, a[510], r, i, s = 0;



int main() {



	cin >> n >> r;




	//Read in everyone's time to hit the water



	for (i = 1; i <= n; i++) {



		cin >> a[i];




	}



	



	//Sort:From smallest to largest, fastest hit first



	sort(a + 1, a + n + 1);



	



	//From r+1Individuals begin to correct the total time spent hitting water for each individual



	//look for a draw (chess)



	for (i = 1; i <= n; i++) {



		if (i >= r + 1) a[i] += a[i - r]; //Equivalent to a[i]=a[i]+a[i-r];



		s = s + a[i];



	}



	



	cout << s;



	



	return 0;



}

interceptor missileThe number of systems solved for the

Title Description

A certain country has developed a missile interception system in order to defend itself against enemy missile attacks. But this missile interception system has a flaw: although its first shot can reach any altitude, each subsequent shot cannot go higher than the previous one.
Suppose that one day the radar catches an incoming missile from an enemy country. Since the system is still in the trial stage, there is only one system, so it is possible that not all missiles will be intercepted.
Input the altitudes of n missiles in sequence (the altitude data given is a positive integer not greater than 30,000) and calculate the minimum number of such missile interceptor systems that would be required if all missiles were to be intercepted.
For example: there are 8 missiles flying at the heights of
389 207 175 300 299 170 158 165
Then 2 systems are needed to intercept, and the optimal solutions for the missiles they can intercept are: System 1: Intercept 389 207 175 170 158
System 2: Interception 300 299 165

importation

Two lines, the first indicating the number of incoming missiles n (n<=1000)

The second line indicates the heights of n missiles flying in sequence

exports

Minimum number of systems to intercept all missilesk

example

importation




8




389  207  175  300  299  170  158  165

exports

Thoughts:

1, when the missile is coming, assuming that the height of the missile is x, find the shortest of the systems that can be intercepted in the a array to do so
2. If you can't find such a system: open a new system intercept and set the height of the new system to x
3. If it can be found (find the 1st system that can intercept, which is the shortest): because the height of the missile interception system must be incremental
Intercept with the 1st system that can be intercepted and set the height of that system to x. Finally, look at how many systems are required




#include <bits/stdc++.h>





using namespace std;



 




//p: represents the subscripts found to be able to intercept the system




//k: stands for how many systems




//x: represents the height of each system



int a[1100],n,i,j,x,p,k = 0;



int main() {



	cin>>n;




	//Number of circulating missiles



	for(i = 1;i <= n;i++){



		cin>>x;




		p = -1;//Suppose we don't find it.



		//Find the first system in the k-set1A system capable of intercepting



		for(j = 1;j <= k;j++){



			//Finding the first1A system capable of intercepting



			if(a[j] >= x){



				p = j;



				break;



			}



		}



		



		//If you find a system interception



		if(p != -1){



			a[p] = x;



		}else{



			//implementation of new system



			k++;



			a[k] = x;//Update system height



		}



	}



	



	cout<<k;



	return 0;



}