题解：P13372 [GCJ 2011 #1C]

我们的旗舰要从0号星球快递到N号星球，路上要依次经过1,2,...N-1号星球。正常情况下飞船速度是0.5秒差距/小时（好慢啊！）。

不过我们可以选择在一些星球上建加速器（最多建L个），每个加速器建造需要t小时（可以同时建多个）。建好加速器的星球出发的飞船速度会变成1秒差距/小时（快了一倍！）。

关键点在于：如果在飞船航行过程中某个星球的加速器建好了，飞船可以立即加速！

先计算每个星段的距离（注意是循环的）
计算如果不建加速器的总时间
找出哪些星段建加速器收益最大（能省最多时间）
优先在这些地方建加速器

3. 具体实现

CPP

#include<iostream>
using namespace std;
int main(){
    int T;
    cin>>T;
    for(int x=1;x<=T;x++){
        int L,t,N,C;
        cin>>L>>t>>N>>C;
        int a[1005];
        for(int i=0;i<C;i++)cin>>a[i];
        
        //计算每个星段的距离
        long long d[1000005];
        for(int i=0;i<N;i++){
            d[i]=a[i%C];
        }
        
        //计算总时间
        long long total=0;
        for(int i=0;i<N;i++){
            total+=d[i]*2; //默认速度0.5，所以时间乘以2
        }
        
        //计算可以节省的时间
        long long save=0;
        long long built=0;
        long long time_elapsed=0;
        for(int i=0;i<N;i++){
            if(built>=L)break;
            if(time_elapsed>=t){
                save+=d[i]; //可以节省d[i]时间
                built++;
            }
            time_elapsed+=d[i]*2;
        }
        
        cout<<"Case #"<<x<<": "<<total-save<<endl;
    }
    return 0;
}

4. 代码解释

输入处理：读取测试用例，循环处理每个case
距离计算：根据给定的循环模式生成每个星段的距离
总时间计算：假设不建加速器，速度为0.5，所以时间=距离×2
最优解计算：
- 按顺序检查每个星段
- 如果加速器能在飞船到达前建好(t <= 当前累计时间)
- 就使用加速器，节省时间
输出结果：总时间减去节省的时间

CAUTION:

距离数组大小：N可以达到1e6，要开足够大的数组（题目说N≤1e6）
时间计算：注意t可能很大(1e11)，要用long long
加速器使用时机：一定要在飞船到达前建好才能用

其实可以不用存所有距离，因为C≤1000，可以循环使用。不过为了代码清晰，我还是存下来了。

题解：P13372 [GCJ 2011 #1C]

文章操作

3. 具体实现

4. 代码解释

相关推荐

评论

题解：P13372 [GCJ 2011 #1C]