数据结构与算法-一维前缀和_随笔

数据结构与算法-一维前缀和

条件：求一维区间和
题目：无
原理：无

代码：

#include 
#include 
#include   //sort
#include 
#include 
#include   //双端队列，头可插，尾可插
#include 
#include 
#include 
#include 
#include 
#include 
#include  //数值的限制范围
//(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
using namespace std;

class Solver {
    //通用属性
public:
    Solver() {
        //取消和c输出输入的同步，加快读取
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    //通用方法
public:
    void SaveCpp(string name) const {

        fstream input;
        fstream output;

        input.open("moota.cpp", ios::in);
        const string file = name + ".cpp";
        output.open(file.c_str(), ios::out);

        char c = 'O';
        while (!input.eof()) {
            input.get(c);
            output << c;
        }

        input.close();
        output.close();

    }

protected:
    //待实现方法
    virtual void BeginPlay() {
    };

    virtual void Playing() {
    };

    virtual void EndPlay() {
    };
public:
    //外观模式
    void Play() {
        BeginPlay();
        Playing();
        EndPlay();
    }
};

class SpecialSolver : public Solver {
public:
    typedef long long lld;
    static const lld MAX = static_cast(1e6);
    static const lld INF = static_cast(1e18);
private: //实例属性
    lld n, m;
private: //实例方法
    //sum1D存的是前i个数的和
    //求i-j的区间和的话 (i<=j)
    //sum1D[i-1],表示前i-1个数的和
    //sum1D[j],表示前j个数的和
    //那么：sum1D[j]-sum1D[i-1]剩下的就是i到j区间的和，这样就求出区间和了。
    lld sum1D[MAX];
protected:
    virtual void BeginPlay() override {
        Solver::BeginPlay();
        cin >> n >> m;
        lld pre = 0;
        for (lld i = 1; i <= n; ++i) {
            cin >> pre;
            sum1D[i] = sum1D[i - 1] + pre;
        }
    };

    virtual void Playing() override {
        Solver::Playing();
        lld l, r;
        while (m--) {
            cin >> l >> r;
            cout << sum1D[r] - sum1D[l - 1] << "n";
        }
    };

    virtual void EndPlay() override {
        Solver::EndPlay();

    };
};

SpecialSolver specialSolver;

int main() {
    //注意改名字
    //specialSolver.SaveCpp("一维前缀和模板");
    specialSolver.Play();
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5611156.html

数据结构与算法-一维前缀和

发表评论

评论列表（0条）