UOJ Easy Round #7 天路 简单的近似算法

题目大意

给定一个长度为$n$的序列，对于每个$2$~$n$的长度，输出长度为$i$的区间中最大值减最小值的最小值是多少，允许答案有$5%$的误差。

$n leq 10^5$
$a_i leq 10^6$

解题思路

一眼看上去这题并不可做，但是有个很关键的信息就是答案允许有$5%$的误差。也就意味着当答案较大时，允许的误差也很大。那么假如我们把误差充分利用，那么答案只可能是$1.05^{k}$，并且也要满足$1.05^{k}leq max_{a_i}$，可以计算出可能的答案只有280多个，对于每种答案，我们只需用单调队列记录最大最小值，那么我们就可以确定在满足误差为$1.05^k$下每个右边界$r$可以对应的最左边的左边界$l$，然后更新$r-l+1$区间对应的答案$ans[r-l+1]$，$ans[i] = min(ans[i],ans[i+1])$以后就是答案。总的复杂度就是$O(300n)$。

程序

//YxuanwKeith
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 5;

int n, l1, r1, l2, r2, a[MAXN], Max[MAXN], Min[MAXN], ans[MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    memset(ans, 60, sizeof ans);
    for (int d = 0; d < 1000000; d = max(d + 1, (int)(1.05 * d) - 2)) {
        l1 = l2 = 1, r1 = r2 = 0;
        int l = 1;
        for (int r = 1; r <= n; r ++) {
            while (l1 <= r1 && a[Min[r1]] > a[r]) r1 --;
            while (l2 <= r2 && a[Max[r2]] < a[r]) r2 --;
            Min[++ r1] = Max[++ r2] = r;
            while (a[Max[l2]] - a[Min[l1]] > d) {
                if (Min[l1] == l) ++ l1;
                if (Max[l2] == l) ++ l2;
                l ++;
            }
            ans[r - l + 1] = min(ans[r - l + 1], a[Max[l2]] - a[Min[l1]]);
        }
    }
    for (int i = n; i >= 2; i --) {
        ans[i] = min(ans[i], ans[i + 1]);
        if (ans[i] == ans[0]) ans[i] = 1000000;
    }
    for (int i = 2; i <= n; i ++)
        printf("%dn", ans[i]);
}

最后

以上就是欢呼电话为你收集整理的UOJ Easy Round #7 天路 简单的近似算法的全部内容，希望文章能够帮你解决UOJ Easy Round #7 天路 简单的近似算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。