1.空调
思路
1.区间同时加减 1，可以转换成一个差分数组两个端点的操作
2.用 p 减去 t 数组，得到要消除的数组 a，对 a 求差分数组
3.差分数组一正一负为一个操作，因为是把这个原数组区间加上了 1，单独的正负为一个操作
4.总共需要的操作就是差分数组里 max(正数和, 负数和)
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], t[N], a[N];
int n;int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &p[i]);for(int i = 1; i <= n; i++){scanf("%d", &t[i]);p[i] -= t[i];}int pos = 0, neg = 0;for(int i = 1; i <= n; i++){a[i] = p[i] - p[i - 1];if(a[i] > 0) pos += a[i];else neg -= a[i];}printf("%d", max(pos, neg));return 0;
}
2.差分
思路
模板题
// 模板1
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);b[i] = a[i] - a[i - 1];}int l, r, c;while(m--){scanf("%d%d%d", &l, &r, &c);b[l] += c;b[r + 1] -= c;}for(int i = 1; i <= n; i++){a[i] = a[i - 1] + b[i];printf("%d ", a[i]);}return 0;
}// 模板2
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m;int insert(int l, int r, int c){a[l] += c;a[r + 1] -= c;
}int main(){scanf("%d%d", &n, &m);int x;for(int i = 1; i <= n; i++){scanf("%d", &x);insert(i, i, x);}int l, r, c;while(m--){scanf("%d%d%d", &l, &r, &c);insert(l, r, c);}for(int i = 1; i <= n; i++){a[i] += a[i - 1];printf("%d ", a[i]);}return 0;
}
3.差分矩阵
思路
模板题
// 模板1
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
int n, m, q;int main(){scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &a[i][j]);b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];}}int x1, y1, x2, y2, c;while(q--){scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];printf("%d ", a[i][j]);}printf("\n");}return 0;
}// 模板2
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
int n, m, q;int insert(int x1, int y1, int x2, int y2, int c){a[x1][y1] += c;a[x2 + 1][y1] -= c;a[x1][y2 + 1] -= c;a[x2 + 1][y2 + 1] += c;
}int main(){scanf("%d%d%d", &n, &m, &q);int x;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &x);insert(i, j, i, j, x);}}int x1, y1, x2, y2, c;while(q--){scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);insert(x1, y1, x2, y2, c);}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];printf("%d ", a[i][j]);}printf("\n");}return 0;
}
4.棋盘
思路
取反就是把这个区域都加上 1，每个位置如果和为偶数，那就是没变，和为奇数就是反了
#include<iostream>
using namespace std;
const int N = 2e3 + 10;
int a[N][N], b[N][N];
int n, m;int main(){scanf("%d%d", &n, &m);int x1, y1, x2, y2;while(m--){scanf("%d%d%d%d", &x1, &y1, &x2, &y2);b[x1][y1]++;b[x2 + 1][y1]--;b[x1][y2 + 1]--;b[x2 + 1][y2 + 1]++;}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){a[i][j] = (a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j]) & 1;printf("%d", a[i][j]);}printf("\n");}return 0;
}
5.重新排序
思路
用差分统计每个位置被加了多少次，加的越多的位置选择越大的数
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;
long long res1, res2;int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);scanf("%d", &m);int l, r;while(m--){scanf("%d%d", &l, &r);b[l]++;b[r + 1]--;}for(int i = 1; i <= n; i++) b[i] += b[i - 1];for(int i = 1; i <= n; i++) res1 += 1ll * a[i] * b[i];sort(a + 1, a + n + 1);sort(b + 1, b + n + 1);for(int i = 1; i <= n; i++) res2 += 1ll * a[i] * b[i];printf("%lld", res2 - res1);return 0;
}
