例题
1、硕鼠的交易
题目描述

Problem Description
小老鼠准备了M磅的猫粮，准备去和看守仓库的猫做交易，因为仓库里有小老鼠喜欢吃的五香豆。

仓库有N个房间；
第i个房间有J[i] 磅的五香豆，并且需要用F[i]磅的猫粮去交换；
老鼠不必交换该房间所有的五香豆，换句话说，它可以用 F[i] a% 磅的猫粮去换取J[i] a%磅的五香豆，其中a是一个实数。

现在，请帮忙计算一下，小老鼠最多能够得到多少磅的五香豆？

Input
输入包含多组测试用例。
每组测试数据首先一行是2个非负整数M和N，接着的N行，每行分别包含2个非负整数J[i]和F[i]。
输入数据以两个-1结束。
题目保证所有的数据不超过1000.

Output
请计算并输出小老鼠最多能够得到的五香豆数量。
每组数据输出一行，保留3位小数。
————————————————

                        版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/m0_60284156/article/details/122669451
`

include<bits/stdc++.h>

using namespace std;
struct node{
double a;
double b;
double c;
}stu[200];
bool cmp(node x,node y){
return x.c > y.c;
};
int main(){
int m,n;
cin >> m >> n;
for(int i=0;i<n;i++){
cin >> stu[i].a >> stu[i].b;
}
for(int i=0;i<n;i++){
stu[i].c=((stu[i].a)/(stu[i].b));
}
sort(stu,stu+n,cmp);
double ans=0.0;
for(int i=0;i<n;i++) {
while ((stu[i].b > 0)&&(m>0)) {
ans += stu[i].c;
stu[i].b--;
m--;
}
}
cout << fixed << setprecision(3) << ans << endl;
return 0;
}
`
2.田忌赛马
题目描述

Problem Description

“田忌赛马”是中国历史上一个著名的故事。

大约2300年前，齐国大将田忌喜欢和国王赛马，并且约定：每赢一场，对方就要付200元。

假设已知田忌和国王的各自马匹的速度都不相同，请计算田忌最好的结果是什么。

Input
输入包含多组测试样例。
每组样例的第一行是一个整数n(n <= 1000),表示田忌和国王各自参赛的马匹数量。
接下来一行的n个整数表示田忌的马的速度，再接下来一行的n个整数表示国王的马的速度。
n为0时，表示输入数据的结束。

Output
每组数据输出一行，表示田忌最多能够赢得的金额。
`

include<bits/stdc++.h>

using namespace std;
int a[2010],b[2010];
bool cmp(int x,int y){
return x>y;
}
int main(){
int m;
int ans=0;
cin >> m;
for(int i=0;i<m;i++){
cin >> a[i];
}
sort(a,a+m,cmp);
for(int i=0;i<m;i++){
cin >> b[i];
}
sort(b,b+m,cmp);
int i,j;
int n=m;
for(i=0,j=0;i<m&&j<n;i++,j++){
if(a[i]>b[j]){
ans++;
}
else{
if(a[m-1]>b[j]){
ans++;
i--;
m--;
}
else{
i--;
m--;
}
}
}
cout << ans*100 << endl;
return 0;
}
`
3.事件序列问题（时间最长）
Problem Description

已知N=12个事件的发生时刻和结束时刻（下表，并已按结束时刻升序排序）。一些在时间上没有重叠的事件可以构成一个事件序列，如{2,8,10}，事件序列包含的事件数目，称为该事件序列的长度。编程找出一个最长的事件序列。

Input Description

第一行输入一个整数0<N<1000，表示事件的数量。
接下来输入N行，输入两个数begin[i]，end[i]，分别表示时间的发生时刻与结束时刻，0<=i<N。

Output Description

输出最长的时间序列。

Sample Input

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

{0,1,5,8,10}
————————————————

原文链接：https://blog.csdn.net/m0_74242327/article/details/131106989

`

include<bits/stdc++.h>

using namespace std;
struct node{
int begin;
int end;
}stu[1010];
bool cmp(node x,node y){
return x.end < y.end;
}
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> stu[i].begin >> stu[i].end;
}
sort(stu,stu+n,cmp);
int ans=1;
node s[1010];
s[0].begin=stu[0].begin;
s[0].end=stu[0].end;
int mark=0;
for(int i=1;i<n;i++){
if(stu[i].begin>=s[mark].end){
mark++;
s[mark].begin=stu[i].begin;
s[mark].end=stu[i].end;
ans++;
}
}
cout << ans << endl;
return 0;
}
`
3.搬桌子（数量最多）
https://blog.csdn.net/m0_62121252/article/details/122766732?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171004964516800226550457%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=171004964516800226550457&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_alltop_positive~default-1-122766732-null-null.142^v99pc_search_result_base2&utm_term=%E6%90%AC%E6%A1%8C%E5%AD%90&spm=1018.2226.3001.4187

`

include<bits/stdc++.h>

using namespace std;
int main(){
int i,j;
int max;
int t;
cin >> t;
int arr[200];
for(i=0;i<t;i++){
int n;
cin >> n;
for(int k=0;k<200;k++){
arr[k]=0;
}
for(j=0;j<n;j++){
int s,d;
cin >> s >> d;
s=(s-1)/2;
d=(d-1)/2;
if(s>d){
int temp;
temp=s;
s=d;
d=temp;
}
for(int w=s;w<=d;w++){
arr[w]++;
}
max=-1;
for(int w=0;w<200;w++){
if(arr[w]>max){
max=arr[w];
}
}
}
cout << max*10 << endl;
}
return 0;
}
`
4.可图性判定

例题

`

`