# A watch TV

### Title Description

When the summer vacation comes, Xiao Ming can finally watch TV happily. But Xiao Ming likes too many programs. He hopes to see as many complete programs as possible.
Now he gives you the broadcasting schedule of his favorite TV programs. Can you help him arrange it reasonably?

### input

The input contains multiple sets of test data. The first line of each group is an integer n (n < = 100), indicating the total number of programs Xiao Ming likes.
Next N lines, input two integers si and ei (1 < = i < = n) in each line to represent the start and end time of the ith program. In order to simplify the problem, each time is represented by a positive integer.
When n=0, the input ends.

### output

For each group of input, output the number of TV programs that can be seen completely.

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

5

### Code submission

```#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=110;
struct Inteval{
int x,y;
}I[maxn];
bool cmp(Inteval a,Inteval b){
if(a.x!=b.x) return a.x>b.x;
else return a.y>b.y;

}
int main()
{
int n;
while(scanf("%d",&n),n!=0){
for(int i=0;i<n;i++){
scanf("%d%d",&I[i].x,&I[i].y);
}
sort(I,I+n,cmp);
int ans=1;
int lastX=I[0].x;
for(int i=0;i<n;i++){
if(I[i].y<=lastX){
lastX=I[i].x;
ans++;
}
}
printf("%d\n",ans);
}

return 0;
}

```

This problem belongs to interval greed in algorithm notes

# B taxi fare

### Title Description

The taxi pricing rules of a city are as follows: 10 yuan for starting 4km, even if your journey does not exceed 4km; For the next 4 kilometers, 2 yuan per kilometer; Then 2.4 yuan per kilometer. Even if the last part of the trip is less than 1 kilometer, it will be charged as 1 kilometer.
A passenger can reasonably arrange the way of taking a taxi according to the number of kilometers to minimize his taxi fare.
For example, if the whole journey is 16 kilometers, passengers should divide the journey into two parts of the same length, each part costs 18 yuan, a total of 36 yuan. If you take a taxi, it will cost 37.2 yuan.
Now I'll give you the kilometers of the whole trip. Please calculate the minimum cost of taking a taxi.

### input

The input contains multiple sets of test data. Enter a positive integer n (n < 10000000) for each group to represent the kilometers of the whole journey.
When n=0, the input ends.

### output

For each set of inputs, the output costs the least. Keep one decimal place if necessary.

3
9
16
0

10
20.4
36

### Code submission

```#include <iostream>
#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
int dis;
while(scanf("%d",&dis),dis!=0){
double sum = 0;
if(dis == 0) return 0;
if(dis <= 4) sum = 10;
else if(dis > 4 && dis <= 8) sum += 10 + (dis - 4)*2;
else
{
while(dis > 8)
{
sum += 18;
dis -= 8;
}
if(dis <= 4) sum += 2.4 * dis;
else sum += 10 + (dis - 4) * 2;
}
if(sum - (int)sum == 0) printf("%d\n", (int)sum);
else printf("%.1f\n", sum);

}

return 0;
}

```

### Problem solving ideas

At first, I didn't quite understand the analogy that topic 16 is divided into two eight kilometers, such as how to divide 38. Later, I found that no matter how much it is, it is mostly divided into eight kilometers.

# C To Fill or Not to Fill

It's hard to take a hole

# D Repair the Wall

It's hard to take a hole

It's hard to take a hole

# F miasma

### Title Description

Youming's character is facing the test of playing the game——
The valley was filled with terrible miasma. As a result of this, the air is full of toxins. Once inhaled into the body, the whole body will fester and die.
Fortunately, Xiao Ming had prepared the antidote materials (all-purpose potions of various concentrations) in advance. Now you just need to configure the concentration in different proportions.
It is now known that Xiaoming carries n kinds of universal potions with the same volume V and the concentration Pi%. And we know that in view of the miasma in the valley at that time, we only need to select some or all of the universal potions, and then configure potions with a concentration of no more than W% to detoxify.
The question now is: how to configure this medicine to get the maximum volume of currently available antidotes?
Special note: due to the limitation of equipment in the valley, only one existing medicine can be mixed with another (i.e. the operation of taking only a part of one medicine cannot occur).

### input

The first row of input data is an integer C, which represents the number of groups of test data;
Each group of test data contains two lines. First, one line gives three positive integers n, V, w (1 < = n, V, w < = 100);
The next line is n integers, representing the concentration PI% (1 < = Pi < = 100) of N potions.

### output

For each group of test data, please output an integer and a floating point number;
The integer represents the maximum volume of the antidote, and the floating-point number represents the concentration of the antidote (rounded to 2 decimal places);
If the antidote that meets the requirements cannot be prepared, please output 0.00.

2
1 35 68
1
2 79 25
59 63

35 0.01
0 0.00

### Algorithm idea

Learn from what you see from other bloggers
The greedy idea of this question is very simple. We need the potion with the largest total volume, so we should choose the one with small concentration to mix together, so that there will be more water and more volume

It should also be noted that the concentration of liquid medicine obtained by mixing small concentration with large concentration must be between the two concentrations

We sort the input concentrations from small to large

The first step is to look at the current minimum concentration. If the current concentration has exceeded the required concentration, we will exceed the required concentration no matter how we mix (because we order from small to large). At this time, we can't prepare potions

If the current concentration meets the requirements, we can calculate whether the concentration after mixing the next bottle meets the conditions. If so, we can mix and test the next concentration If not, do not mix and give up mixing

# G change

### Title Description

Xiao Zhi went shopping in the supermarket and bought something no more than 100 yuan. The cashier wants to change as little money as possible.
The denominations of banknotes are divided into five types: 50 20 10 5 1. If you know how much money n to give Xiao Ming, please choose the scheme with the least amount of banknotes. 1<=n<=99;

### input

There are multiple groups of data 1 < = n < = 99;

### output

For each note whose quantity is not 0, output their face value * quantity, and then add it up to output

25
32

201+51
201+101+1*2

### Code submission

```#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
int n;
int money[5]={50,20,10,5,1};
while(scanf("%d",&n),n!=0){
while(n!=0){
int ans[5]={0};
while(n>=50){
ans[0]++;
n=n-50;
}
while(n<50&&n>=20){
ans[1]++;
n=n-20;
}
while(n<20&&n>=10){
ans[2]++;
n=n-10;
}
while(n<10&&n>=5){
ans[3]++;
n=n-5;
}
while(n<5&&n>=1){
ans[4]++;
n=n-1;
}
int count = 0;
for(int i=0;i<=4;i++)
{
if(ans[i]>0)
count++;
}
for(int i=0;i<=4;i++)
{
if(ans[i]>0)
{
if(count>1)
{
printf("%d*%d+",money[i],ans[i]);

}
else
{
printf("%d*%d",money[i],ans[i]);
}
count--;
}
}
}
}

return 0;
}

```

Keywords: Algorithm greedy algorithm