题解：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 了。

考虑这样一组样例：

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

我的输出：

2 100 100 1

正确输出：

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

#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;
}

提交记录