yzm0325 @ 2023-02-11 17:56:28
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 5000010;
int a[maxn], dif[maxn], ans[maxn];
int n, p, minn = 200000000;
void differ() { // 差分
for(int i = 1; i <= n; i++) {
if(i == 1) dif[i] = a[i];
else dif[i] = a[i] - a[i - 1];
}
return;
}
void prefix() { // 前缀和
for(int i = 1; i <= n; i++) ans[i] = dif[i] + ans[i - 1]; // 这样也不用担心越界,数组开得大
return;
}
int main() {
memset(a, 0, sizeof(a));
memset(dif, 0, sizeof(dif));
memset(ans, 0, sizeof(ans));
cin >> n >> p;
for(int i = 1; i <= n; i++) cin >> a[i];
differ(); // 差分初始化
int x, y, z;
for(int i = 1; i <= p; i++) {
cin >> x >> y >> z;
dif[x] += z, dif[y] -= z; // 差分的好处,直接降一个循环
}
prefix();
for(int i = 1; i <= n; i++) if(ans[i] < minn) minn = ans[i];
cout << minn;
return 0;
}
为什么不对呢?
by yzm0325 @ 2023-02-11 17:56:47
可以直接@我
by yzm0325 @ 2023-02-11 18:02:00
改了一下,
#include <iostream>
using namespace std;
const int maxn = 5000010;
int a[maxn], dif[maxn], ans[maxn];
int n, p, minn = 200000000;
void differ() { // 差分
for(int i = 1; i <= n; i++) {
if(i == 1) dif[i] = a[i];
else dif[i] = a[i] - dif[i - 1];
}
return;
}
void prefix() { // 前缀和
for(int i = 1; i <= n; i++) ans[i] = dif[i] + ans[i - 1]; // 这样也不用担心越界,数组开得大
return;
}
int main() {
cin >> n >> p;
for(int i = 1; i <= n; i++) cin >> a[i];
differ(); // 差分初始化
int x, y, z;
for(int i = 1; i <= p; i++) {
cin >> x >> y >> z;
dif[x] += z, dif[y] -= z; // 差分的好处,直接降一个循环
}
prefix();
for(int i = 1; i <= n; i++) if(ans[i] < minn) minn = ans[i];
cout << minn;
return 0;
}
why???
by yzm0325 @ 2023-02-11 18:04:52
#include <iostream>
using namespace std;
const int maxn = 5000010;
int a[maxn], dif[maxn], ans[maxn];
int n, p, minn = 200000000;
void differ() { // 差分
for(int i = 1; i <= n; i++) dif[i] = a[i] - dif[i - 1];
return;
}
void prefix() { // 前缀和
for(int i = 1; i <= n; i++) ans[i] = dif[i] + ans[i - 1];
return;
}
int main() {
cin >> n >> p;
for(int i = 1; i <= n; i++) cin >> a[i];
differ(); // 差分初始化
int x, y, z;
for(int i = 1; i <= p; i++) {
cin >> x >> y >> z;
dif[x] += z, dif[y] -= z; // 差分的好处,直接降一个循环
}
prefix();
for(int i = 1; i <= n; i++) if(ans[i] < minn) minn = ans[i];
cout << minn;
return 0;
}
by yzm0325 @ 2023-02-11 18:06:41
自己改对了。
#include <iostream>
using namespace std;
const int maxn = 5000010;
int a[maxn], dif[maxn], ans[maxn];
int n, p, minn = 200000000;
void differ() { // 差分
for(int i = 1; i <= n; i++) dif[i] = a[i] - a[i - 1];
return;
}
void prefix() { // 前缀和
for(int i = 1; i <= n; i++) ans[i] = dif[i] + ans[i - 1];
return;
}
int main() {
cin >> n >> p;
for(int i = 1; i <= n; i++) cin >> a[i];
differ(); // 差分初始化
int x, y, z;
for(int i = 1; i <= p; i++) {
cin >> x >> y >> z;
dif[x] += z, dif[y + 1] -= z; // 差分的好处,直接降一个循环
}
prefix();
for(int i = 1; i <= n; i++) if(ans[i] < minn) minn = ans[i];
cout << minn;
return 0;
}
此贴终。