贪心与sort的cmp(返回常数或表达式)
让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]...
·
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;
}
输出结果:
原1:9 6 7 5 8 变化后1:8 5 7 6 9
原2:8 5 7 6 9 变化后2:9 6 7 5 8
原3:9 6 7 5 8 变化后3:8 5 7 6 9
原4:8 5 7 6 9 变化后4:5 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;
}
输出结果:
原1:9 6 7 5 8 变化后1:9 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;
}
更多推荐



所有评论(0)