Article From:

Although Farmer John has no problems walking around the fair to collect prizes or see the shows, his cows are not in such good shape; a full day of walking around the fair leaves them exhausted. To help them enjoy the fair, FJ has arranged for a shuttle truck to take the cows from place to place in the fairgrounds.

FJ couldn’t afford a really great shuttle, so the shuttle he rented traverses its route only once (!) and makes N (1 <= N <= 20,000) stops (conveniently numbered 1..N) along its path. A total of K (1 <= K <= 50,000) groups of cows conveniently numbered 1..K wish to use the shuttle, each of the M_i (1 <= M_i <= N) cows in group i wanting to ride from one stop S_i (1 <= S_i < E_i) to another stop E_i (S_i < E_i <= N) farther along the route.

The shuttle might not be able to pick up an entire group of cows (since it has limited capacity) but can pick up partial groups as appropriate.

Given the capacity C (1 <= C <= 100) of the shuttle truck and the descriptions of the groups of cows that want to visit various sites at the fair, determine the maximum number of cows that can ride the shuttle during the fair.

It’s not much for Farmer John to go around the bazaar, cash prizes and watch the show, but his cows lack exercise very much – they’ll be exhausted if they’re going to spend the whole day at the bazaar. So in order for the dairy cows to have a good time at the fair, John was going to let them drive instead. howeverJohn Wood was rich, and his rented bus could only run straight on the market once, and could only stop at N (1 < N < 20,000) locations (all represented by a number between 1 and N). Now the cows are divided into groups K (1 K or less than 50000), and group I has Mi.(1 less than Mi N) cows, they want to run from Si to Ti (1 Si&lt, Ti = N).

Due to the limited capacity of the shuttle bus, it may not be able to carry all the cows who want to ride, at this time also allows a small part of the cows to ride the shuttle bus separately. John learned through the survey that the capacity of the shuttle bus is C (1 < C < 100), please help John to plan a plan to meet as many cows as possible.

Input output format


The first line consists of three integers: K, N and C, separated from each other by spaces.

The second line to the K+1 line: in line i+1, you will be told the information of cow I in group I: Si, Ei and Mi.

This is separated by spaces.



The first line: the maximum number of cows that can take a shuttle bus.


Examples of input and output

Input sample #1:

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1
Output sample #1:



The shuttle bus can send 2 cows from 1 to 5, 3 cows from 5 to 8, 2 cows from 8 to 14, 1.

Cows were sent from 9 to 12, 1 cows from 13 to 14, and 1 cows to 14 from 14.


Originally wanted to use this problem to practice a line segment tree, but instead found the greed of this pit and then filled the situation?????

never mind….Let’s write two of them.

First, a strong Amway blog! Click here until I see this, and I finally understand the greedy train of thought.

We’re not going to enumerate how to fill the entire trip 1-n, but once (from 1-k) to each group of cows into the spare seats.

For each group of cows, we have to choose the last place to get off.Closest toThe next starting seat will be connected.

Record the last time node occupied by each seat in h[c].

After reading in, Group K cattle first sort by the earliest end as the first keyword, the earliest start as the second keyword, and then start greedy enumeration

Each time the earliest seats are removed from H [c], you can sit down if they are empty before the current enumeration of group I begins

Sit down a cow, ans++

For specific greedy proof, please see the link above.

The code is as follows:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define N 50010
 7 using namespace std;
 8 struct node
 9 {
10     int m,s,t;
11 }e[N];
12 bool cmp(node a,node b)
13 {
14     if(a.t!=b.t)
15         return a.t<b.t;
16     return a.s<b.s;
17 }
18 bool cmmp(int a,int b)
19 {
20     return a>b;
21 }
22 int n,k,c,ans;
23 int h[150];//The time at which I is occupied.
24 int main()
25 {
26     scanf("%d%d%d",&k,&n,&c);
27     for(int i=1;i<=k;i++)
28         scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].m);
29     sort(e+1,e+k+1,cmp);
30     for(int i=1;i<=k;i++)
31     {
32         sort(h+1,h+c+1,cmmp);
33         for(int j=1;j<=c&&e[i].m;j++)
34         {
35             if(h[j]<=e[i].s)
36             {
37                 ans++;
38                 h[j]=e[i].t;
39                 e[i].m--;
40             }
41         }
42     }
43     printf("%d",ans);
44     return 0;
45 }

View Code


Then where is the line tree?

If the data water is available, we can rank each choice of H [c], but if the data is serious, the process can be maintained with a line segment tree.

This is the code:



I watched for another hour and didn’t respond.

It’s QAQ




I finally understand!!!!

After joining the line tree, the whole process came back to my earliest thought!!!!

It means that the interval of maintenance is the length of the whole road of 1~n, and each group looks as a sub interval.

Subintervals are used to cover the total interval, and then the maximum number of subintervals that can be obtained if the thickness of the overlapping part (i.e. the number of overlapping intervals) does not exceed C (of course, each interval has repeated m_i times)

Then it becomes interval query maximum and interval modification.

Whether the maximum value of each check is more than c, and compared with the number of cattle in this group, cumulative answer, the number of cattle in the interval +;

OK, the code will be more ovo tomorrow.

(It’s so psychedelic that three days ago the idea was a positive solution but didn’t know what to do with it and wanted to write Greed 2333 333 first.

Leave a Reply

Your email address will not be published. Required fields are marked *