sort的使用和贪心算法
sort函数 先简单介绍一下sort函数
sort对给定区间所有元素进行排序,头文件是#include
Sort函数有三个参数：
- 第一个是要排序的数组的起始地址。
- 第二个是结束的地址（最后一位要排序的地址的下一地址）
- 第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。
1.整数数组直接从小到大排列
#include
#includeusing namespace std;
//输入：
//先输入数组长度 n
//然后再输入n个整数
//输出
//从小到大顺序输出数组
int main()
{
int i,n,a[200];
scanf("%d",&n);
for(i=0;
i 2.整数数组从小到大排序(用cmp)
#include
#include
using namespace std;
//输入：
//先输入数组长度 n
//然后再输入n个整数
//输出
//从小到大顺序输出数组
int cmp(int x,int y){
return x 【sort的使用和贪心算法】3.整数数组从大到小排序，这个只需要把2中的cmp的不等号换一下就好了
#include
#include
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 4.结构体数组简单排序(单属性)
#include
#includeusing 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 5.结构体数组双属性排序
#include
#includeusing 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 6.结构体数组双属性排序2//所有的结构体排序都可以把以上的cmp函数，写成结构体运算符重载operator<
#include
#include
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 7.字符串数组排序（char字符串）
#include
#include
#include
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 8.字符串数组排序（string 字符串）
#includeusing namespace std;
int main()
{
printf("请输入要排序的字符串:\n");
string s;
cin>>s;
sort(s.begin(),s.end());
printf("排序完后的字符串为:\n");
cout< 最优装载问题 1.给出N个物体，第一个物体重量为W1
2.选择尽量多的物体，使得总重量不超过C
思路
拿最小的？？
尽量多装质量小的？？这正确吗？
假如有这么一种方案是没有优先装质量小的，那么我们始终可以
把它换成质量更小的，而数目没有变化
因此，我们可以确定：我们只需要把所有物体按重量从小到大排序，依次选择
每个物体，直到放不下为止，就能得到最优解了
虽然证明不是特别严谨，要真正证明的话用反证法
下面上代码:
#include
#include
#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-1次即可
每次加完后可能就不是从小到大了，所以每次加完都要再次排序
#includeusing namespace std;
long longsum,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< 问题三:国王游戏
恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左右手分别写下一个整数，
国王自己也在左右手上各写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，
所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的
左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多
的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣所获得的奖金尽可能少。注意，
国王的位置始终在队伍的最前面。（金币数大于1）
【输入格式】
第一行为一个整数n（1<=n<=1000）表示大臣的人数
第二行为两个整数a，b（0 接下来的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
以a[i]*b[i]为关键字排序即可
同时统计答案时一定不要忘了写高精度
#include
#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];
} 推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量