本文主要是介绍数据结构与算法-一维差分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 条件:无
- 题目:无
- 原理:无
- 代码:
/**
* mootable
*/
#include <iostream>
#include <iomanip>
#include <algorithm> //sort
#include <map>
#include <queue>
#include <deque> //双端队列,头可插,尾可插
#include <string>
#include <cstring>
#include <stack>
#include <cmath>
#include <fstream>
#include <ctime>
#include <climits> //数值的限制范围
//(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<lld>(1e6);
static const lld INF = static_cast<lld>(1e18);
private: //实例属性
lld n, m;
private: //实例方法
lld sub1D[MAX];
protected:
virtual void BeginPlay() override {
Solver::BeginPlay();
cin >> n >> m;
lld pre = 0, cur = 0;
for (lld i = 1; i <= n; ++i) {
cin >> cur;
sub1D[i] = cur - pre;
pre = cur;
}
};
virtual void Playing() override {
Solver::Playing();
lld index;
while (m--) {
cin >> index;
lld num = 0;
for (lld i = 1; i <= index; ++i) {
num += sub1D[i];
}
cout << num;
}
};
virtual void EndPlay() override {
Solver::EndPlay();
};
};
SpecialSolver specialSolver;
int main() {
//注意改名字
//specialSolver.SaveCpp("一维差分模板");
specialSolver.Play();
}
这篇关于数据结构与算法-一维差分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!