Programming Problem 1:AgriculturalHarvest Competition (Greedy) In an agricultural powerhouse, a grand harvest competition is held annually where farmers harvest their crops and compete for the title of harvest champion based on yield. The participating farmers must display their crop yields over several days, with the final winner determined by the total accumulated yield.
This year, the harvest competition has reached its final day, and the farmers have already accumulated their harvests from the previous days. However, the yield on the final day will be decisive, as the scoring for that day will follow special rules: the first-place farmer will receiveN points, the second place will receive N-1 points, and so on, with the last place receiving 1 point. There will be no ties on the final day.
Given the current accumulated scores of each farmer, calculate how many farmers still have the potential to win the final harvest championship before the last day of competition begins (the final champion may have ties).
Input Format:
· The first line contains an integer N, representing the total number of participating farmers.
· The next N lines containN farmers’ current accumulated scores.
Sample 1:38109 Output:3
Sample 2:6605550302010 Output:2Thought Analysis: The first thought for this problem should be greedy, when determining if a person can potentially win the competition, we should first give that person the maximum score -> N, and then compare it with those who originally had higher scores, we should give them the lowest scores possible, which are 1, 2, 3…. This way, that person can win. We first sort each person’s score in ascending order, then iterate through each one, giving them the highest score first, and then giving the highest person 1, the second highest 2….. and so on until we reach the previous person, without needing to care about those who have lower scores than this person, as they cannot surpass him.Reference Code:
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){ int N; cin >> N; vector<int> cnt; for (int i = 0; i < N; i++) { int x; cin >> x; cnt.push_back(x); } int ans = 1; // Final answer sort(cnt.begin(), cnt.end()); // Iterate from the first to the second last for (int i = 0; i < N - 1; i++) { int cnt_i = cnt[i] + N; bool f = true; for (int j = N - 1, x = 1; j > i; j--, x++) { // If unable to win if (cnt[j] + x > cnt_i) { f = false; break; } } if (f) { ans++; } } cout << ans << endl; return 0;}Programming Problem 2: Repairing Roads (Greedy)
In a picturesque country, the famous “Golden Avenue” connects various tourist attractions. However, with the surge in tourist numbers, many damaged sections of this avenue have emerged, affecting the travel plans of visitors. To ensure the safety and smooth passage of tourists, the country has decided to repair these damaged sections and temporarily close certain segments. As the traffic management engineer in charge, you need to calculate the minimum total length of road segments that need to be closed for these problem areas to be repaired as soon as possible.
Givenn damaged segment coordinates and the number of segments to be closedm, find a distribution scheme that minimizes the total length of closed segments.
Input Format:
· The first line contains two positive integersn andm（separated by a space,m should not have a space after it）。
· The second line containsn integers representing the coordinates of the damaged segments (the coordinate values are long integers, given in ascending order, and no two points have the same coordinate)（n integers are separated by a space, and there should be no space after the last integer）
Output Format:
Output an integer representing the minimum total length of closed segments.
Sample 1:18 43 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43 Output 1:25Sample1Explanation：
The closed segments are:3-8、14-21、25-31、40-43，the minimum total length of closed segments is6+8+7+4=25.
Note: The closure of segment3-8is illustrated in the following diagram.
Sample 2:8 42 5 6 7 11 12 15 20 Output 2:10Thought Analysis: This problem also uses the greedy algorithm, which essentially separates the defective road segments into m parts, minimizing the distance of the closed segments. Dividing into m segments is equivalent to making m-1 cuts, meaning selecting m-1 positions to split. It is important to note that, as shown in the diagram above, the coordinates are not a single point but a small segment of road. We can first calculate the intervals of each segment, then sort them in ascending order, and select the largest m-1 intervals to make the cuts. The thought process is that the closed segments start from the first defective coordinate and end at the last coordinate, regardless of how we cut, there will always be m-1 intervals between adjacent defects, so the final length of the closed segments will be the distance between the first and last minus these m-1 distances, thus we need to maximize these m-1 distances by selecting the largest ones. In simplified terms, there are a total of n-1 intervals, and we do not need the largest m-1, so we can sum the first (n-1)-(m-1) intervals after sorting to get the final answer. However, it is important to note that when calculating each segment’s interval, we directly subtract the coordinates, for example, 3 8, we calculate the interval = 7. In reality, there are 8 segments in length, and when we divide into m parts, we will undercount m segment lengths. Some may wonder why we are undercounting the total interval count rather than the segment count? Because although we undercounted each time, when two adjacent defective segments are placed in the same segment, one of the undercounted ones will be canceled out, for example, between 3 8 we undercounted 3, but if 8 14 and they are in the same segment, we still only undercounted 3 because the 8 in 14 is counted in the front. In summary, we only need to sum the first (n-1)-(m-1) intervals and then add the number of segments m to get the answer!Reference Code:
#include <iostream>#include <vector>#include <algorithm>using lli = long long int;using namespace std;int main(){ vector<lli> data; int n, m; cin >> n >> m; lli x, a; cin >> x; for (int i = 1; i < n; i++) { cin >> a; data.push_back(a - x); x = a; } sort(data.begin(), data.end()); lli ans = 0; for (int i = 0; i < n - m; i++) { ans += data[i]; } cout << ans + m << endl; return 0;}Today, I will first introduce the two greedy problems. These two problems are not too difficult, but they are also not easy to think of. The first problem seems harder to prove correctness than the second. Regarding greedy problems, it is about achieving global optimality through local optimality. As for the proof of correctness? I don’t know if it needs to be slowly proven with mathematical principles.