C++ cmp比较函数

在写一道贪心算法题中涉及到的cmp 比较函数

img

🔗P2240 部分背包问题 - 洛谷

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;

struct gold
{
 double w,v,p; 
}a[105];  //w,v,p: 重量,价值,单价

bool cmp(gold a, gold b)
{
 return a.p > b.p;
} //单价从大到小排序

int main(){
 int n,c; cin>>n>>c;

 for(int i=0;i<n;i++){
     cin >> a[i].w >> a[i].v;
     a[i].p = a[i].v/a[i].w;
 }
 sort(a,a+n,cmp);
 double sum=0.0;
 for(int i=0;i<n;i++){
     if(c >= a[i].w){//第i种金币比背包容量小
         c -= a[i].w;
         sum += a[i].v;
     }
		else{//第i种金币很多，直接放满背包
         sum += c*a[i].p;
         break;
     }
 }
 printf("%.2f",sum);
	return 0;
}

🔗例题 318. 最大单词长度乘积 - 力扣（LeetCode）

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
 bool isLegal(const string str1, const string str2){
     for(auto ch1 :str1){
         for(auto ch2:str2){
             if(ch1==ch2){
                 return false;
             }
         }
     }
     return true;
 }

 //静态成员函数
 static bool cmp(const string& x, const string& y)
 {
     return x.size()>y.size();
 }

 int maxProduct(vector<string>& words) {
     //按照字符串长度降序排列
     sort(words.begin(),words.end(),cmp);

     int max=0;

     for(int i=0;i<words.size();i++){
         for(int j=0;j<words.size();j++){
             if(max>=words[i].size()*words[j].size()){
                 break;
             }
             if(isLegal(words[i],words[j])){
                 max=words[i].size()*words[j].size();
             }
         }
     }
     return max;
 }
};

Tips

在自定义cmp函数时候，要保证 static bool cmp(const string& x, const string& y)非静态成员函数作为 sort 函数的比较函数，而非静态成员函数需要通过类的实例来调用。为了解决这个问题，可以使用一个静态成员函数，或者将比较函数定义为一个普通的全局函数。

1. 非静态成员函数（普通成员函数）：

  • 访问权限： 可以访问类的所有成员，包括非静态成员变量和函数。

  • 示例：

    1
    2
    3
    4
    5
    6
    7
    8
    cppCopy codeclass MyClass {
    public:
        int nonStaticVariable;

        void nonStaticMemberFunction() {
            // 可以访问非静态成员变量和其他非静态成员函数
        }
    };

2. 静态成员函数：

  • 访问权限： 只能访问类的静态成员变量和其他静态成员函数。不能直接访问非静态成员。

  • 示例：

    1
    2
    3
    4
    5
    6
    7
    8
    cppCopy codeclass MyClass {
    public:
        static int staticVariable;

        static void staticMemberFunction() {
            // 只能访问静态成员变量和其他静态成员函数
        }
    };

本题考虑运算效率，甚至判断循环结束的一个<改为<=也会提高代码的效率。