库尔勒网站,asp.net开发的网站,合肥网站建设过程,上海有名的科技公司2021-12-2 序列查询新解 分段处理 用乘法代替加法减少时间复杂度#xff08;思想是离散化#xff09;2021-12-2 序列查询新解 分段处理 用乘法代替加法减少时间复杂度#xff08;思想是离散化#xff09; 2021-12-2 序列查询新解 分段处理 用乘法代替加法减少时间复杂度思想是离散化2021-12-2 序列查询新解 分段处理 用乘法代替加法减少时间复杂度思想是离散化 2021-12-2 序列查询新解 分段处理 用乘法代替加法减少时间复杂度思想是离散化思路解题过程超时的完整代码100分的完整代码 2021-12-2 序列查询新解 分段处理 用乘法代替加法减少时间复杂度思想是离散化
这个题目挺有意思比之前几年我做过的都要有些难但是也不是难吧就是没有见过这种的然后就想不到怎么去优化时间复杂度。
一开始我以为题目的优化思路是预处理就是提前算好f和g然后再减在一起算出sum我还抱着侥幸心理以为 1 0 9 10^9 109的复杂度不会超时但是最后还是超时了此时我就是黔驴技穷了我只是想到在 1 0 9 10^9 109的基础上优化但是没有想到怎么用直接使用 1 0 5 10^5 105分段进行计算。然后看了别人的思路才有了思路。希望考试不要出现这种情况因为考试可没有别人的思路给你看。
思路
这题的思路不同于之前的第二题实用什么的差分啊什么二分搜索啊什么动态规划啊都没有使用到。而是不同寻常的使用了分段的思想。
我一开始的想法是使用一个数组把f全部算出来但是发现并不行会超时并且也没有用空间来换取时间但是其中有很多重复的加法可以用乘法替换。
我们拿到一个问题一般是要将问题规约成更小的问题那么如何规约就会导致问题的时间复杂度和空间复杂度不同这题你要是想用空间换时间就是把临时搜索的数据存储下来后边可以不搜索直接使用的思想不太行而是要减少计算的次数基本就是将加换成乘。
那么怎么将加换成乘呢就是将相同的加合并对应这个题目就是算f和g的时候我们可以把一段区间内的加变成一次乘法。 那么这个区间就是当g和f 相同的区间g的变化是有规律的f 的变化也是有规律的我们就是判断一个区间是不是f和g都不变化那么我们就可以直接加上区间长度和 ∣ f − g ∣ |f-g| ∣f−g∣的乘积 。
解题过程
我首先就是按照我想的那种思路写了一种代码直接就70分了剩下全部超时了 然后我就想找一种优化的方法比如使用常数级优化O2优化等全都是超时可以发现只要 复杂度是 1 0 9 10^9 109怎么优化也没有用的。 测试只有一个for循环 1 0 9 10^9 109次什么也不干就会超时 然后看了别人的思路说使用分段的思想我瞬间就明白了就写代码 但是发现错误不太行原来是没有使用long long
改用了long long 后就可以了
超时的完整代码
#include bits/stdc.h
using namespace std;
int n, N;
int a[100001];
int f[100000001];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin n N;for (int i 1; i n; i){cin a[i];}int top 1;int r N / (n 1);long long sum 0;for (int i 0; i N; i){if (i a[top]){f[i] top - 1;}else{f[i] top;if (top n)top;else{sum abs(i / r - top);continue;}}sum abs(i / r - f[i]);}cout sum;return 0;
}100分的完整代码
#include bits/stdc.h
using namespace std;
int n, N;
int a[100001];
int main()
{cin n N;int maxa -1;for (int i 1; i n; i){cin a[i];maxa max(a[i], maxa);}int r N / (n 1);int f 0;long long sum 0;for (int i 1; i n; i){// 判断g和f谁先变// f是遇到元素才变 g是隔r个数就变的f i - 1;int length a[i] - a[i - 1];int gl a[i - 1] / r;int gr (a[i] - 1) / r; // 不包括右端点因为右端点f的值已经变化了if (gr gl) // 如果这个区间g的值没有变化{sum abs(f - gl) * length;}else // 如果g有变化那么再分区间{int left a[i - 1]; // 不断更新区间的左端点 知道超过f不变的区间while (left a[i]){int length min(a[i], (gl 1) * r) - left;sum abs(f - gl) * length;// 更新状态left (gl 1) * r;gl;}}}if (maxa N) // 遍历超出了a的数此时f恒等于n g还是原来的变化规律{int f n;int left a[n];int gl left / r;while (left N){int length min(N, (gl 1) * r) - left;sum abs(f - gl) * length;// TODO更新状态left (gl 1) * r;gl;}}cout sum;return 0;
}
