大家来共同交流一下第一题思路。。【百度之星吧】

发布时间：2024-12-10 13:27

感觉这次比上次难，复赛A只会两道（只不过第二道没敢用网络流，用裸贪心骗分的。。）
先说一下复赛B中自己A题的算法吧：
看到题目第一反映是想写个递推，用dp解。。。但是数据量太大了。。。。。O(100000^2)显然超时。。。寻找更优化算法。。。。
于是乎，过了一会儿，发现一个性质：如果在区间(l,r)内有一个比l和r都高的点，那么这个点是必定会经过的，所以可以将原问题分解成两部分(l, pos), (pos,r)分别解这两个问题然后合并就可以了。其他情况也类似，都有这个特点：如果l可以直接到r，那么直接计算就可以了，肯定是最小值；否则得话选(l+1,r-1)中最高的一个点，然后分别求解子问题，然后合并（就是相加）就可以了。
不知道这个思路是否正确，但稍微证明了一下感觉它起码不会比最优情况差 = =！也没有举出什么反例，代码如下，如有不同解法，欢迎交流：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100010;
typedef long long llg;
llg n, ans, h[N];
int tree[N<<2];
void build_tree(int u, int l, int r)
{
    int mid = (l+r)>>1, tmp = u<<1;
    if(l == r)
    {
        tree[u] = l;
        return;
    }
    else
    {
        build_tree(tmp, l, mid);
        build_tree(tmp+1, mid+1, r);
        if(h[tree[tmp]] > h[tree[tmp+1]]) tree[u] = tree[tmp];
        else tree[u] = tree[tmp+1];
    }
}
int Getmax(int u, int l, int r, int a, int b)
{
    int tmp = u<<1, mid = (l+r)>>1;
    if(a==l && b==r) return tree[u];
    else
    {
        if(b <= mid) return Getmax(tmp, l, mid, a, b);
        else if(a > mid) return Getmax(tmp+1, mid+1, r, a, b);
        else
        {
            int tmp1, tmp2;
            tmp1 = Getmax(tmp, l, mid, a, mid);
            tmp2 = Getmax(tmp+1, mid+1, r, mid+1, b);
            if(h[tmp1] >= h[tmp2]) return tmp1;
            else return tmp2;
        }
    }
}
llg merge(int l, int r)
{
    llg tmp1, tmp2;
    if(l == r) return 0;
    if(l+1 == r)
    {
        if(h[l] >= h[r]) return 0;
        else return h[r]-h[l];
    }
    int pos = Getmax(1, 0, n, l+1, r-1);
    if(h<h[l] || h<h[r])
    {
        if(h[l]>=r-l && h[l]>=h[r]) return 0;
        if(h[l]>=r-l && h[l]<h[r]) return h[r]-h[l];
    }
    tmp1 = merge(l, pos);
    tmp2 = merge(pos, r);
    return tmp1+tmp2;
}
int main()
{
    int i;
    scanf("%lld", &n);
    for(i = 0; i <= n; i++) scanf("%lld", &h[i]);
    build_tree(1, 0, n);
    ans = merge(0, n);
    printf("%lld\n", ans);
    return 0;
}

czz19891012

直接用堆,找出之前区间里面能跳到这个点的高度最高的那个.
我瞎写的.

Moon_1st

补充一下，查找最大值时用到了线段树，所以最坏时间复杂度是O(n*logn)

无解的名字

不是堆单调队列单调递减的单调队列
除了入栈出栈每次还要从队首元素开始把不能跳到下一个点的点删除这样每次新来的点默认取队首即可
然后倒着扫一遍。。。
我是这么想的。。。
话说就想出来一道回家种地抱孩子去了。。。

coolypf

我用的贪心，和DP的程序对拍了半天，发现没错就叫上去了

贴吧用户_0J6N8ay

这个有反例吧。
8 3 1 1 1 1 1 1 2 7
如果按照你说的拆解方式，则是8=>3, 3=>7
这样得到的解是6
如果选择8=>2, 2=>7
那么解是5，更优。

KenKwok0

大概同六楼的算法，O(n)。
试过 Random Test Case，答案跟 LZ 的一样。
#include <cstdio>
int n, h[1 << 17], q[1 << 17], qa, qb, st;long long ans;
int main() { scanf("%d", &n) == 1; for (int i = 0; i <= n; ++i) scanf("%d", h + i); qa = qb = -1; ans = 0; st = 0; while (st != n) { for (int i = (qa == qb ? st + 1 : q[qb] + 1); i <= n && i <= st + h[st]; ++i) { if (qa == qb) q[++qb] = i; else { while (qa != qb && h[q[qb]] < h[i]) --qb; if (qa == qb || q[qb] + h[q[qb]] < i + h[i]) q[++qb] = i; } } ans += (h[st] < h[q[qa + 1]] ? h[q[qa + 1]] - h[st] : 0); st = q[++qa]; } printf("%lld\n", ans); return 0;}

tecmoo

怎么说呢，贪心和DP很难有不同点，LS给你个我生成数据的程序，要是能和DP一样就差不多OK了。
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
int main()
{
    freopen("in.txt","w",stdout);
    int i,j,k,n;
    srand(time(0));
    k=300;
    while(k--)
    {
        n=rand()%500+1;
        printf("%d\n",n);
        for(i=1;i<=n+1;i++)
            printf("%d ",(rand()%15+1));
        printf("\n");
    }
    return 0;
}

KenKwok0

十楼的 test data 厉害！我试了十几个 n=10000 的 test data 都找不到反例……

zlq_for_astar

同单调队列
我来证明下吧
可以发现这个游戏取决于要请可能少的从上到下
不妨假定这个算法不是最优的
那么也就是说对于某个点i 存在点j 比能到达i 的最远点k更优
首先可以发现能到达点i的点的高度必然从头到尾单调递减
所以有H[k] > H[j]
那么不妨假设点j之前转移中第一个在k点前面的p点转移过来
很显然有H[P] >= H[k]
那么显然有 p点到j点的代价至少是 H[p] - H[j]
然而 p点可到k之后意味着p点必然可以到k 那么p点到k的代价至多是H[p] - H[k]
由此可知k点一定比j点优
故证毕

网址：大家来共同交流一下第一题思路。。【百度之星吧】 https://mxgxt.com/news/view/125293

上一篇：波姬小丝是如何成为全球审美标杆的

下一篇：五一吃瓜明星爆料：星途背后的秘密

大家来共同交流一下第一题思路。。【百度之星吧】

相关内容

随便看看

最新实时动态

热点实时动态

专题

推荐实时动态