算法提升篇——operator重载

引言

最近在看算法题打算备战七月份的马蹄和明年的蓝桥（今年由于囊肿羞涩没有参加——有点后悔，学校的奖学金还是很多的），写来写去发现还是只能做些简单的题，重复的循环和判断让我觉得涉足更难的贪心，但一上来就遇到了一名猛将[[P7990 USACO21DEC] Closest Cow Wins S - 洛谷]。我觉得是时候开启operator了

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int num, actor1, actor2;
    cin >> num >> actor1 >> actor2;
    vector<pair<long long,long long>> grass(num);
    vector<long long> Actor1(actor1);
    for(int i = 0; i < num; i++)
        cin >> grass[i].first >> grass[i].second;
    for(int i = 0; i < actor1; i++)
        cin >> Actor1[i];
    sort(grass.begin(),grass.end());
    sort(Actor1.begin(),Actor1.end());
    vector<pair<long long,long long>> segments;
    
    if(actor1 == 0) {
        long long sum = 0;
        for(int i = 0; i < num; i++)
            sum += grass[i].second;
        segments.push_back({sum, 1});
    }
    else {
        long long sum = 0;
        for(int i = 0; i < num; i++) {
            if(grass[i].first < Actor1[0]) {
                sum += grass[i].second;
            }
        }
        if(sum > 0)
            segments.push_back({sum, 1});
            
        for(int j = 0; j < actor1-1; j++) {
            for(int i = 0; i < num; i++) {
                if(grass[i].first > Actor1[j] && grass[i].first < Actor1[j+1]) {
                    long long dist1 = abs(grass[i].first - Actor1[j]);
                    long long dist2 = abs(grass[i].first - Actor1[j+1]);
                    if(dist1 < dist2) {  
                        segments.push_back({grass[i].second, 1});
                    }
                }
            }
        }
        
        sum = 0;
        for(int i = 0; i < num; i++) {
            if(grass[i].first > Actor1[actor1-1]) {
                sum += grass[i].second;
            }
        }
        if(sum > 0)
            segments.push_back({sum, 1});
    }
    
    sort(segments.begin(), segments.end(), greater<pair<long long,long long>>());
    long long ans = 0;
    for(int i = 0; i < min(actor2, (int)segments.size()); i++) {
        ans += segments[i].first;
    }
    cout << ans << endl;
    return 0;
}

非常朴实的vector开数组，限定条件——最后发现只能过一个点，剩下的全部超时。当我优化时间复杂度后发现剩下的超时全部报错。让我明白了简单的约束并不能拯救我的分，唯有高级算法才是唯一出路。

搓不出来经典“Orz”看大佬题解，发现了operator重构这个写法。

一、什么是操作符重载？

操作符重载，顾名思义，就是为自定义类型赋予标准操作符的行为。换句话说，你可以定义“加号”、“等号”、“乘号”在你的类对象之间应该做什么。

举个简单的例子(“+”的重构)：

#include <iostream>
using namespace std;

class Point {
private:
    int x, y;

public:
    // 构造函数
    Point(int x = 0, int y = 0) : x(x), y(y) {}

    // 加法操作符重载
    Point operator+(const Point& other) const {
        return Point(this->x + other.x, this->y + other.y);
    }

    // 输出函数
    void display() const {
        cout << "(" << x << ", " << y << ")" << endl;
    }
};

int main() {
    Point p1(2, 3);
    Point p2(4, 5);

    Point result = p1 + p2;  // 触发 operator+ 重载

    cout << "p1 + p2 = ";
    result.display();

    return 0;
}

我们重构(operator)了**’’+”,指定了p1和p2类型为（x, y）** 。此时的+不等同于普通的”+“，而是被定义为**(x + other.x , y + other.y)** 的**result(p类)**。

result是Point 类，其下的display 我们用**result.display ( )**引用。相 **”+”**的操作已在Point result = p1 +p2;中完成，此时输出display中cout << "(" << x << "," << y << ")" << endl;

最后的结果如下图

我们再看一下比较难的例子,取自菜鸟教程的重构例子。当时我第一次了解重构并看了这个例子一头雾水，现在我们一起重新看一下它。

#include <iostream>
#include <vector>
using namespace std;
 
// 假设一个实际的类
class Obj {
   static int i, j;
public:
   void f() const { cout << i++ << endl; }
   void g() const { cout << j++ << endl; }
};
 
// 静态成员定义
int Obj::i = 10;
int Obj::j = 12;
 
// 为上面的类实现一个容器
class ObjContainer {
   vector<Obj*> a;
public:
   void add(Obj* obj)
   { 
      a.push_back(obj);  // 调用向量的标准方法
   }
   friend class SmartPointer;
};
 
// 实现智能指针，用于访问类 Obj 的成员
class SmartPointer {
   ObjContainer oc;
   int index;
public:
   SmartPointer(ObjContainer& objc)
   { 
       oc = objc;
       index = 0;
   }
   // 返回值表示列表结束
   bool operator++() // 前缀版本
   { 
     if(index >= oc.a.size() - 1) return false;
     if(oc.a[++index] == 0) return false;
     return true;
   }
   bool operator++(int) // 后缀版本
   { 
      return operator++();
   }
   // 重载运算符 ->
   Obj* operator->() const 
   {
     if(!oc.a[index])
     {
        cout << "Zero value";
        return (Obj*)0;
     }
     return oc.a[index];
   }
};
 
int main() {
   const int sz = 10;
   Obj o[sz];
   ObjContainer oc;
   for(int i = 0; i < sz; i++)
   {
       oc.add(&o[i]);
   }
   SmartPointer sp(oc); // 创建一个迭代器
   do {
      sp->f(); // 智能指针调用
      sp->g();
   } while(sp++);
   return 0;
}

前面的步骤相同，不同的是利用看起来更高级的创建方法，不在public内直接定义未知数的值，而是用int + 类名 + :: + 变量 + 定义值。此类做法始

1
2
3

class Obj {
   static int i, j; // 声明，但没有分配内存
};

这只是声明了两个静态变量 i 和 j，告诉编译器这个类有这两个静态变量，但没有为它们分配内存。因为静态成员属于类而不是某个对象。普通成员变量每个对象一份，编译器可以在构造对象的时候分配空间。但静态变量是类“共有”的，所以必须由程序员在类外手动定义、初始化，才能真正分配内存空间。

class ObjContainer {
   vector<Obj*> a;
public:
   void add(Obj* obj) { a.push_back(obj); }
   friend class SmartPointer;
};

a：一个 Obj* 类型的 vector，用于存放指向 Obj 的指针。

add()：将对象指针添加到容器中。

friend class SmartPointer;：授予 SmartPointer 类对其私有成员的访问权限。