sort函数
先简单介绍一下sort函数
sort对给定区间所有元素进行排序,头文件是#include <algorithm>
Sort函数有三个参数：
- 第一个是要排序的数组的起始地址。
- 第二个是结束的地址（最后一位要排序的地址的下一地址）
- 第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。
下面详细介绍一下sort的各种用法
1.整数数组直接从小到大排列
#include<algorithm>
#include<cstdio>
using namespace std;
//输入：
// 先输入数组长度 n
// 然后再输入n个整数
//输出
// 从小到大顺序输出数组
int main()
{
int i,n,a[200];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}2.整数数组从小到大排序(用cmp)
#include<algorithm>
#include<cstdio>
using namespace std;
//输入：
// 先输入数组长度 n
// 然后再输入n个整数
//输出
// 从小到大顺序输出数组
int cmp(int x,int y){
return x<y;
}
int main()
{
int i,n,a[200];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n,cmp);
for(i=0;i<n;i++)
printf("%d ",a[i]);
puts("");
return 0;
}3.整数数组从大到小排序，这个只需要把2中的cmp的不等号换一下就好了
#include<algorithm>
#include<cstdio>
using namespace std;
//输入：
// 先输入数组长度 n
// 然后再输入n个整数
//输出
// 从大到小顺序输出数组
int cmp(int x,int y){
return x>y;
}
int main()
{
int i,n,a[200];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n,cmp);
for(i=0;i<n;i++)
printf("%d ",a[i]);
puts("");
return 0;
}4.结构体数组简单排序(单属性)
#include<algorithm>
#include<cstdio>
using namespace std;
//输入：
// 先输入结构体数组长度 n
// 然后再输入n个整数，表示结构体的其中的一个属性q
//输出
// 根据结构体数组的属性q的从大到小顺序，输出结构体数组
struct s{
int q;
int b;
}a[200];
int cmp(s x,s y)
{
return s.q>y.q
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i].q);
}
sort(a,a+n,cmp);
for(i=0;i<n;i++)
{
printf("%d 原位置：%d\n",a[i].q,a[i].b);
}
puts(" ");
return 0;
}5.结构体数组双属性排序
#include<algorithm>
#include<cstdio>
using namespace std;
//输入：
// 先输入结构体数组长度 n
// 然后接下去n行，每行输入两个整数，表示结构体的其中的两个属性p和q
//输出
// 根据p属性的大小进行从大到小排序，在p相等的情况下，则根据q的大小进行从大到小排序
/*
样例输入：
5
3 5
4 7
6 3
4 9
3 2
*/
struct s
{
int p;
int q;
}a[200];
int cmp(s x,s y){
if(x.p==y.p)
return x.q>y.q
return x.p>y.p
}
int main(){
int i,n;
scanf("%d",&n);
for(i=0;i<n,i++)
{
scanf("%d%d",&a[i].p,&a[i].q);
}
sort(a,a+n,cmp);
puts("排序后");
for(i=0;i<n;i++)
{
printf("%d %d\n",a[i].p,a[i].q);
}
puts(" ");
return 0;
}6.结构体数组双属性排序2 // 所有的结构体排序都可以把以上的cmp函数，写成结构体运算符重载operator<
#include<algorithm>
#include<cstdio>
using namespace std;
//输入：
// 先输入结构体数组长度 n
// 然后接下去n行，每行输入两个整数，表示结构体的其中的两个属性p和q
//输出
// 根据p属性的大小进行从大到小排序，在p相等的情况下，则根据q的大小进行从大到小排序
/*
样例输入：
5
3 5
4 7
6 3
4 9
3 2
*/
struct S{
int q;
int p;
bool friend operator <(S a,S b){
if(a.p==b.p) return a.q>b.q;
return a.p>b.p;
}
}a[200];
int main(){
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&a[i].p,&a[i].q);
sort(a,a+n);
puts("排序后:");
for(i=0;i<n;i++)
printf("%d %d\n",a[i].p,a[i].q);
puts("");
return 0;
}7.字符串数组排序（char字符串）
#include<cstdio>
#include<sstring>
#include<algorithm>
using namespace std;
//输入：
// 先输入字符串数组长度 n
// 然后再输入n个字符串
//输出
// 从小到大顺序输出字符串数组
char as[200][50];
int cmp(int x,int y)
{
return strcmp(as[x],as[y])==-1;
}
int main()
{
int i,n,a;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",as[i]);
a[i]=i;
}
sort(a,a+n);
for(i=0;i<n;i++)
{
printf("%s\n",as[a[i]]);
}
return 0;
}8.字符串数组排序（string 字符串）
#include<bits/stdc++.h>
using namespace std;
int main()
{
printf("请输入要排序的字符串:\n");
string s; cin>>s;
sort(s.begin(),s.end());
printf("排序完后的字符串为:\n");
cout<<s<<endl;
return 0;
}最优装载问题
1.给出N个物体，第一个物体重量为W1
2.选择尽量多的物体，使得总重量不超过C
思路
拿最小的？？
尽量多装质量小的？？这正确吗？
假如有这么一种方案是没有优先装质量小的，那么我们始终可以
把它换成质量更小的，而数目没有变化
因此，我们可以确定：我们只需要把所有物体按重量从小到大排序，依次选择
每个物体，直到放不下为止，就能得到最优解了
虽然证明不是特别严谨，要真正证明的话用反证法
下面上代码:
#include<iostream>
#include<algorithm>
#define MAXN 1000005
using namespace std;
int w[MAXN];//每件古董的重量
int main()
{
int c,n;//c:载重量，n古董数
int sum = 0;//装入古董的数量
int tmp = 0;//装入古董的重量
cin >> c >> n;
for(int i= 1; i <= n; ++i)
cin >> w[i];
sort(w+1,w+1+n);
for(int i = 1; i <= n; ++i)
{
tmp += w[i];//这个要在if外面
if(tmp<=c)
sum++;
else
break;
}
cout << sum << endl;
return 0;
}
问题二：合并果子
有N堆果子，每堆果子有自己的果子数AI，每次合并可以将任意两堆果子合并，合并小号的体力
为两堆果子果子数之和
求消耗的最小体力
1<N<10000
思路：
显然，选最小的两堆果子合并N-1次即可
每次加完后可能就不是从小到大了，所以每次加完都要再次排序
#include<bits/stdc++.h>
using namespace std;
long long sum,a[100001],n,d;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
d=n;
sort(a+1,a+n+1);
for(int i=1;i<=d-1;i++)
{
a[1]+=a[2];
for(int j=2;j<=n-1;j++)
a[j]=a[j+1];
sum+=a[1];
n--;
sort(a+1,a+n+1);
// for(int i=1;i<=n;i++)
// cout<<a[i]<<" ";
// cout<<" "<<sum<<endl;
}
cout<<sum<<endl;
return 0;
}问题三:国王游戏
恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左右手分别写下一个整数，
国王自己也在左右手上各写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，
所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的
左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多
的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣所获得的奖金尽可能少。注意，
国王的位置始终在队伍的最前面。（金币数大于1）
【输入格式】
第一行为一个整数n（1<=n<=1000）表示大臣的人数
第二行为两个整数a，b（0<a,b<10000），分别表示国王左手和右手上的整数
接下来的n行，每行为两个整数a，b分别表示每个大臣左手和右手上的整数
【输出格式】
仅一行为一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数
样例及解释
输入：
3
1 1
2 3
7 4
4 6
输出：
2
分析
我们可以枚举每一种情况
1 2 3 => 2(获得奖赏最多的大臣获得的金币数)
1 3 2 => 2
2 1 3 => 2
2 3 1 => 9
3 1 2 => 2
3 2 1 => 9
但是枚举显然不是一个好的做法，因为n挺大，要枚举到死啊，所以显然有好的做法，我们来分析一下
显然在交换前面的数时，后面的数答案是没有变化的，当然对交换的前面的数也没有影响
也就是说相邻两个人位置的交换只会对这两个人产生影响。我们便从这里为切入点，分析调换相邻二元组的顺序对
答案产生的影响
设这两个人的位置为i和i+1，左手数字为a[i]和a[i+]，右手数字为b[i]和b[i+1],两个人的金币
数为w[i]和w[i+1]。
记p[i]=a[1]*a[2]*...*a[i]
则未调换位置时，k1=w[i]=p[i-1]/b[i]; k2=p[i-1]*a[i]/b[i+1]；
有ans1=max{k1,k2};
调换位置后， k3=p[i-1]/b[i+1]; k4=p[i-1]*a[i+1]/b[i];
有ans2=max{k3,k4};
显然k1<k4,k3<k2;
如果ans1<ans2,则必有k2<k4 <=> a[i]*b[i]<a[i+1]*b[i+1]
所以为了让ans取得最小值，我们需要把a[i]*b[i]较小的放在前面，那么我们
以a[i]*b[i]为关键字排序即可
同时统计答案时一定不要忘了写高精度
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int len = 1;//表示高精度数据的长度
int sum[100001] = {0,1};//高精度数据计算结果
struct minister{
ll left;
ll right;
} m[1000001];
bool cmp(minister a,minister b){
return a.left * a.right < b.left * b.right;
}
void multiplicative(ll x){//高精度乘法
for(int i = 1;i <= len; i++){
sum[i] *= x; //各位数乘x,如1111×20 = (1000+100+10+1)×20
}
for(int i = 1;i <= len; i++){
sum[i + 1] += sum[i] / 10;//获得进位,因为相乘结果可能为 10 3 13 4,需转化为 1 0 4 3 4
sum[i] %= 10;
}
len++;//因为是sum[i+1],所以肯定会计算到sum[len+1],所以需要len++
while(sum[len] / 10){//观察最高位是否有进位,因为可能有经过前面的操作后可能有 100 3的情况
sum[len + 1] = sum[len] / 10;
sum[len] %= 10;
len++;
}
//经过前面的一波操作后,最后可能会导致sum[len]的位置上有0,若为0则需要消除
if(sum[len] == 0)
len--;
}
void division(){//高精度除法,这里只需要进行一次操作,所以不需要参数
//思路依旧很简单,如2345/5=(2000+300+40+5)/5,小学生除法
//->2 3 4 5 ->0 23(3 + 2%5*10) 4 5 -> 0 4 34(4 + 23%5*10) 5 -> 0 4 6 45(5 + 34%5*10)
for(int i = len; i >= 1; i--){
sum[i - 1] += (sum[i] % m[n].right * 10);
sum[i] /= m[n].right;
}
//这波操作必然导致一堆前导0，需消除
while(!sum[len]){
len--;
}
//防止除完了
if(len == 0) cout << "1" << endl;
}
int main(){
cin >> n;
cin >> m[0].left >> m[0].right;
for(int i = 1;i <= n; i++)
cin >> m[i].left >> m[i].right;
sort(m + 1, m + 1 + n, cmp);
for(int i = 0;i < n; i++){
multiplicative(m[i].left);
}
division();
for(int i = len; i >= 1; i--)
cout << sum[i];
}