Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

There are several houses on one side of the street. The residents want to plant trees along the road for environmental reasons.

Areas along the road are divided into blocks and numbered 1,2… , n1, 2,… , n1, 2,… , n. Each section is a unit size and can be planted up to one tree.

Each resident wanted to plant some trees in front of the house and assigned three numbers b, E, TB, E, TB, E, T. These three numbers indicate that the resident wants to plant at least TTT trees in the area between BBB and EEE, including BBB and EEE.

The areas where residents want to plant trees can be crossed. Your task is to find the minimum number of trees that satisfy all the requirements.

Input format

The first line of input is an integer representing the number of fields, NNN.

The second line of the input is an integer representing the number of houses HHH.

(I +2)(I +2)(I +2)(I +2)(I +2)(I +2) integers are bi, EI,tib_i, e_i, t_ibi, EI,ti, Represents the third resident who wants to plant at least tit_iti trees between BIB_ibi and EIE_IEi.

The output format

Output a line of integers representing the minimum number of trees.

Input and output examples

The input

6. 8. 9Copy the code

The output

5
Copy the code

Data size and convention

For 100% data, ensure:


1 Or less n Or less 3 x 1 0 4 1 Or less h Or less 5 x 1 0 3 1 Or less b i Or less e i Or less n 1 Or less t i Or less e i – b i + 1 1 n 3 x 10 ^ 4 or less or less \ \ 1 h or less 5 x or less 10 ^ 3 \ \ 1 b_i e_i n \ \ 1 or less or less or less t_i e_i or less or less – b_i \ \ + 1

Directions: For this part, you are allowed 30 minutes

In what way?

Make it a habit to look at data size.

And by looking at the data size, we can actually get a rough idea of how to solve this problem. After all, the author of the problem is n 106n~10^6n 106, you can not easily beat the for loop with violence, then we need to consider the time complexity NLGNNLGNNLGN solution.

So, for example, this problem, the size of the fourth power, looks like it could be solved in n2n^2n2.

Think of a solution… Dynamic programming? Since the request is in the form of an interval, it is not easy to do state transitions….

Greed?

Can you think of it this way: to plant the least number of trees, just plant them in the most overlapping areas possible?

How do you do it? Consider one of the most important ways to be greedy: sorting.

We order all the intervals from smallest to largest by destination. And then we fill in the interval from left to right. We maintain the following sub-problems:

After sorting, each interval will have some overlap on the left and the right, and it’s best that we plant those overlap areas. Let’s say we’ve planted the first i-1 interval and we get to the ith interval, and even though there’s overlap on the left, we definitely don’t have to plant on the left anymore. Why? Because the structure of this subproblem is: after the first I-1 interval is planted, even if the left overlap area is planted, it is equivalent to only contributing to the current interval because the left overlap area has already met the requirements. However, since we have not touched the following sections, we can plant trees one by one from the right to the left in as many overlapping areas as possible, and make contributions to as many sections as possible, to achieve the greedy effect.

A few more words of warning

When sorting intervals, if two intervals have the same end point, which one is the left of the larger one or the left of the smaller one? It’s all the same. Think about it carefully with the above analysis. To be specific, I started from small to large.

The complete code

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cctype> #include <string> #include <cmath> #include <cstring> #include <queue> #include <numeric> #define fru(a, b, c) for (int a = b; a <= c; a++) #define frd(a, b, c) for (int a = b; a >= c; a--) #define fr(a, b) for (int a = 0; a < b; a++) #define pb push_back #define mp make_pair #define sof sizeof using namespace std; using ll = long long; using db = double; const int maxn = 30000 + 5; int arr[maxn]; int ask[maxn][3]; int cmp(const void *a, const void *b) { if (*((int *)a + 1) ! = *((int *)b + 1)) return *((int *)a + 1) - *((int *)b + 1); else return *(int *)a - *(int *)b; } int main() { int n; cin >> n; int h; cin >> h; for (int i = 0; i < h; i++) { int b, e, t; cin >> b >> e >> t; ask[i][0] = b; ask[i][1] = e; ask[i][2] = t; } qsort(ask, h, sizeof(int) * 3, cmp); for (int i = 0; i < h; i++) { int cnt = 0; for (int j = ask[i][0]; j <= ask[i][1]; j++) { if (arr[j]) cnt++; } for (int j = ask[i][1]; j >= ask[i][0] && ask[i][2]>cnt ; j--) { if (! arr[j]) { arr[j] = 1; cnt++; } } } int res = 0; for (int i = 0; i <= n; i++) { if (arr[i]) res++; } cout << res; }Copy the code

conclusion

  • When multiple intervals are encountered, greedy algorithms can be considered.
  • Remember to look at the data size to infer the solution.