题解：B4187 [中山市赛 2024] 糖果共享

这里提供一个迭代的思路。

题意

有

n

个人围成了一圈，第

i

个人会在

t_i

秒获得糖果，在

p_i

秒之后将糖果传递给第

i+1

个人（第

n

个人传递给第

1

个人），有

q

次询问，给你一个

x

，输出第

x

个人最早在什么时候可以得到糖果。

思路

考虑 DP，

dp_i

表示第

i

个同学最早获得糖果的时间。

则得到状态转移方程：

dp_i=\min(dp_i,dp_{i-1}+p_{i-1})

写完代码，一提交，WA 了。

考虑这样一组样例：

CPP

4
100 100 100 1
1 1 1 1
4
1 2 3 4

我的输出：

CPP

2 100 100 1

正确输出：

CPP

2 3 4 1

这是因为当前

i

同学的

dp_i

是由

dp_{i-1}

转移而来的，而在单次从左到右遍历中，

dp_{i-1}

本身可能还未达到最优值，导致

dp_i

的计算基于一个偏大的

dp_{i-1}

，最终使得某些同学的最早时间偏大。

可以记录一个

flag

，如果当前这一轮有最短时间被更新，

flag

就更新成

1

，如果当前这一轮没有更新，那么下一轮也不会更新，

flag

设为

0

，直接退出即可。

关于时间复杂度：

理论上如果一次只更新一个位置的话，时间复杂度是

O(n^2)

的，但是这个题的数据只有

4

个测试点需要更新

2

轮，其他都只要更新

1

轮，所以这份代码也是跑的快到飞起，目前是最优解。

Code

CPP

#include<bits/stdc++.h>
#define double long double
#define bug cout<<"___songge888___"<<'\n';
using namespace std;
int n;
int t[200010],dp[200010];
int p[200010];
int q;
int flag;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        dp[i]=t[i];
    }
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    flag=1;
    while(flag){
        flag=0;
        for(int i=2;i<=n;i++){
            if(dp[i]>dp[i-1]+p[i-1]){
                flag=1;
                dp[i]=dp[i-1]+p[i-1];
            }
        }
        if(dp[1]>dp[n]+p[n]){
            flag=1;
            dp[1]=dp[n]+p[n];
        }
    }
        
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        cout<<dp[x]<<'\n';
    }
    return 0;
}

提交记录

题解：B4187 [中山市赛 2024] 糖果共享

文章操作

题意

思路

Code

相关推荐

评论

题解：B4187 [中山市赛 2024] 糖果共享