sort的cmp返回1或0时:

#include<bits/stdc++.h>
#define LL long long
#define fo(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int a[5]={9,6,7,5,8};
void pri(int a[5]){fo(i,0,5)cout<<a[i]<<" ";}
int cmp1(int x,int y){return 1;}
int cmp2(int x,int y){if(x>y)return 1;}//main里连续调用2次 
int cmp3(int x,int y){
    if(x<y)return 1;//可看成不换 
    else return 0;//可看成换
}//这才是升序(反之 > 就是降序) 
int main(){
    cout<<"原1:"; pri(a);{ sort(a,a+5,cmp1);cout<<"变化后1:";pri(a);cout<<endl; }
    cout<<"原2:"; pri(a);{ sort(a,a+5,cmp2);cout<<"变化后2:";pri(a);cout<<endl; }
    cout<<"原3:"; pri(a);{ sort(a,a+5,cmp2);cout<<"变化后3:";pri(a);cout<<endl; }
    cout<<"原4:"; pri(a);{ sort(a,a+5,cmp3);cout<<"变化后4:";pri(a);}
    return 0;
}

输出结果:

19 6 7 5 8 变化后18 5 7 6 928 5 7 6 9 变化后29 6 7 5 839 6 7 5 8 变化后38 5 7 6 948 5 7 6 9 变化后45 6 7 8 9

总结:

sort的cmp返回1/0时,要想排序,需要考虑if-else配对情况,所以这种方法略有复杂

sort的cmp直接return表达式时:

#include<bits/stdc++.h>
#define LL long long
#define fo(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int a[5]={9,6,7,5,8};
void pri(int a[5]){fo(i,0,5)cout<<a[i]<<" ";}
int cmp1(int x,int y){return x>y;}
int main(){
    cout<<"原1:"; pri(a);{ sort(a,a+5,cmp1);cout<<"变化后1:";pri(a);}
    return 0;
}

输出结果:

19 6 7 5 8 变化后19 8 7 6 5

总结: 这种方法比较简单

例1

牛客网例题:每日一报

ac代码:

#include<bits/stdc++.h>
#define LL long long
#define fo(i,a,b) for(int i=a;i<b;i++)
using namespace std;
struct stu{
    int a,b;
    float c;
}ar[100];
int cmp(stu x,stu y){
    if(x.a==y.a){
        if(x.c==y.c)
            return x.b<y.b;//学号作为第三关键字升序(要最先排序)
        return x.c>y.c;//体温作为第二关键字降序
    }
    return x.a>y.a;//报送日期作为第一关键字降序(要最后排序)
}
int main(){
    int n,count=0;
    cin>>n;
    fo(i,0,n){
        cin>>ar[i].a>>ar[i].b>>ar[i].c;
        if(ar[i].c>=38.0)count++;
    }
    cout<<count<<endl; 
    sort(ar,ar+n,cmp);//cmp不写会报错 
    fo(i,0,n){
        if(ar[i].c>=38.0){
            cout<<ar[i].a<<" "<<ar[i].b<<" ";
            printf("%.1f\n",ar[i].c);
        }
    }
    return 0;
}

核心代码(cmp部分):

int cmp(stu x,stu y){
    if(x.a==y.a){
        if(x.c==y.c)
            return x.b<y.b;//学号作为第三关键字升序(要最先排序)
        return x.c>y.c;//体温作为第二关键字降序
    }
    return x.a>y.a;//报送日期作为第一关键字降序(要最后排序)
}

例2

在这里插入图片描述
使用微扰法,考虑两个冰块,当 v 1 t 1 + v 2 ( t 1 + t 2 ) < = v 2 t 2 + v 1 ( t 1 + t 2 ) v_{1}t_{1}+v_{2}(t_{1}+t_{2})<=v_{2}t_{2}+v_{1}(t_{1}+t_{2}) v1t1+v2(t1+t2)<=v2t2+v1(t1+t2)时融化量最小,即 v 2 t 1 < = v 1 t 2 v_{2}t_{1}<=v_{1}t_{2} v2t1<=v1t2,之后按此排序后计算即可

注意搬运冰块的时候是不会融化的(题干未说,可以通过样例看出来)

代码:

#include <bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout<<#x<<":"<<x<<endl;
#define f(i,a,n) for(int i=a;i<n;++i)
#define ff(i,a,n) for(int i=a;i<=n;++i)
#define IN freopen("E:\\信竞\\信竞文件夹\\in_c.TXT","r",stdin);
#define OUT freopen("E:\\信竞\\信竞文件夹\\out_c.TXT","w",stdout);
const int INF=0x3f3f3f3f;
using namespace std;
typedef long long ll;
//
const int N=1e5+5;
struct bi{
    ll t,d;
    bool operator< (bi b){
        return t*b.d<d*b.t;
    }
}a[N];
int n;
int main(){
    cin>>n;
    f(i,0,n){
        cin>>a[i].t>>a[i].d;
    }
    sort(a,a+n);
    ll res=0,t0=0;
	f(i,0,n){
		res+=(t0)*a[i].d;
		t0+=a[i].t;
	}
    cout<<res<<endl;
    return 0;
}

运算符重载严谨一些要写成:

bool operator< (const bi b)const{
    return t*b.d<d*b.t;
}

也可以写cmp函数:

bool cmp(bi t1,bi t2){
    return t1.t*t2.d<t1.d*t2.t;
}

或者:

bool cmp(bi t1,bi t2){
    if (t1.t*t2.d<t1.d*t2.t) return true;
    else return false;
}
Logo

开源鸿蒙跨平台开发社区汇聚开发者与厂商,共建“一次开发,多端部署”的开源生态,致力于降低跨端开发门槛,推动万物智联创新。

更多推荐