qsort()中cmp函数用法：
https://blog.csdn.net/m0_51627418/article/details/121246105?spm=1001.2014.3001.5502
一、活动安排问题
输入样例
11
1 4
3 6
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
输出样例
4
分析：
对每一个活动按照占用会场时间排序，其实也是按照结束时间来排序的。因为安排一个活动后，在这个活动结束时间之前，是不能在安排活动的。就可以分为结束时间相等和不等两种情况来判断。这里的cmp：如果结束时间一样，就找是开始时间小的（这样占用时间最短）；如果结束时间不一样就是就找最早结束的。
这里的代码实现原理：
cmp()会有三种返回值（以qsort为例）:
1、返回一个正数：a排列在b之后；
2、返回0：a、b相等；
3、返回一个负数：a排在b之前；
过题C语言代码：
// #include<bits/stdc++.h>
// using namespace std;
#include<stdio.h>
#include<stdlib.h>
int cmp(const void* a,const void* b){
if(((int *)a)[1]==((int *)b)[1]) return ((int *)a)[0]-((int *)b)[0];
else return ((int *)a)[1]-((int *)b)[1];
}
int main(){
int n;
scanf("%d",&n);
int a[n+5][2];
for(int i = 0; i <n;i++) scanf("%d%d",&a[i][0],&a[i][1]);
qsort(a,n,2*sizeof(int),cmp);
int count = 1, j = 0;
for(int i = 1; i <n;i++){
if(a[i][0]>=a[j][1]){
j = i;
count ++;
}
}
printf("%d",count);
return 0;
}
二、最优装载问题
输入样例
8 30
4 10 7 11 3 5 14 2
输出样例
5
就是一个选最小没啥可说的
解题代码：
//#include<bits/stdc++.h>
//using namespace std;
#include<stdio.h>
#include<stdlib.h>
int cmp(const void* a,const void* b){
return *((int*)a) - *((int*)b);
}
int main(){
int n,m,cnt = 0;
scanf("%d%d",&n,&m);
int a[n+10];
for(int i = 0; i < n;i++){
scanf("%d",&a[i]);
}
qsort(a,n,sizeof(int),cmp);
int sum= 0;
for(int i = 0; i < n; i++){
sum += a[i];
if(sum>m) break;
cnt++;
}
printf("%d",cnt);
return 0;
}
三、背包问题(贪心版本 可拆分版本)
输入样例
3 15
5 10
2 8
3 9
输出样例
60
分析：
其实这因该是一个思维题吧。可以拆分，就直接每个物品都拆为单位重量价值。然后查找最大的单位重量价值，乘以背包容量，就是背包所能装的最大价值。
过题代码：
#include<stdio.h>
#include<algorithm>
#include<math.h>
//#include<bits/stdc++.h>
//using namespace std;
int main(){
int n,m;
scanf("%d%d",&n,&m);
double x,y;
double a[n+10];
for(int i = 0; i <n;i++){
scanf("%d%d",&x,&y);
a[i] = y/x;
}
int t = 0;
for(int j = 1,i=0;j<n;j++){
if(a[j]>a[i]) t = a[i],a[i]= a[j],a[j]= t;
}
int ans = m*a[0];
printf("%d",ans);
return 0;
}
五、删数问题
输入样例
178543 4
输出样例
13
思路：
过题代码：
#include<stdio.h>
#include<algorithm>
#include<math.h>
//#include<bits/stdc++.h>
//using namespace std;
int main(){
char ch[240];
int a[250],cnt = 0;
scanf("%s",ch);
for(int i = 0; ch[i]!='\0';i++){
cnt ++;
a[i] = ch[i] -'0';
}
int ccnt =0,s = 0;
printf("%d",a[0]);
for(int i = 1; i <cnt;i++){
if(ccnt<4&&a[s]<a[i]) ccnt++;
else{
printf("%d",a[i]);
s = i;
}
}
return 0;
}
