P10132 [USACO24JAN] Cannonball B题解

miaoyu2022 · 2024-02-06 16:58:21 · 题解

传送门

思路

看到这题，一下就将暴力模拟代码打了出来。

拿了80分。

优化

看了官方题解才想出来的

不难发现，当能量为 k 时，最多跳 \lfloor \frac{n}{k} \rfloor 次便会跳出或跳到下一个跳板。所以，在不出现死循环时，最多跳 \sum_{i=1}^n \frac {n}{i} \approx n\lg(n) 次便会跳出，而出现死循环后她将不会再次击破目标。也就是说当跳完 n\lg(n) 时，便可停止继续循环模拟。

复杂度 O(n\lg(n))。

Code

AC记录

#include <bits/stdc++.h>
using namespace std;
int n,s,f=1,k=1,ans=0,t=0;
struct node
{
    int q,v;
    bool flag;
}a[100005];
int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++) scanf("%d %d",&a[i].q,&a[i].v),a[i].flag=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i].q==1) t++;
    }
    for(int i=1;i<=n*log(n)+5&&s>=1&&s<=n&&ans!=t;i++)
    {
        if(a[s].q==0) f=-f,k+=a[s].v;
        if(a[s].q==1&&a[s].v<=k&&a[s].flag) a[s].flag=0,ans++;
        s+=f*k;
    }
    printf("%d",ans);
    return 0;
}