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.
sample input
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
sample output
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.
sample input
3
9
16
0
sample output
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
E FatMouse's Trade
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.
sample input
2
1 35 68
1
2 79 25
59 63
sample output
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
Code submission
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
sample input
25
32
sample output
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;
}