模考T4题解

经验分享区
1

我们可以逆向思考从终点反向推导。

可以发现，每一段运输过程中，我们需要保证下一段能继续运输且尽量装满。例如，当运输次数为 1 次时，从补给点到下一位置 d_1 运输距离 内消耗的苹果数加上到达该位置剩余的苹果数要等于 K ；当运输次数为 3 次（往返运输）时，运输距离 d_2 内消耗的苹果数加上到达该位置剩余的苹果数要等于 2K ，以此类推。

那么我们可以用 l 来存储还剩下的距离， a 记录消耗的苹果总数， t 表示当前阶段的运输次数。

每次循环我们要计算每次运输能前进的最大距离 maxn ，即 \frac{K}{2t-1} 其中 2t-1 表示在该阶段运输苹果需要走的单程次数。

  • 如果 maxn 大于等于 l，说明当前阶段可以直接到达目的地，此时消耗的苹果数为 l*(2*t-1)，并跳出循环。
  • 否则，不能直接到达，设置补给点，消耗的苹果数为 maxn*(2*t-1)，更新剩余距离 l 为 l-maxn，并将运输次数 t 加 1 。

最后对 a 向上取整就是答案，即 ceil(a) 但是大家会发现这样 AC 不了，这是为什么呢？

因为我们还需要加上 (int)ceil(a) 否则输出会带数学符号输出会 WA！

代码框架：

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
I AK IOI;
int n,k;
int main(){
    /*输入*/
    double l=n,a=0;
	int t=1;
    while(l>0){
        double maxn=k*1.0/(2*t-1);//运输能前进的最大距离
        if(maxn>=l){//如果可以直接到达目的地
            a+=l*(2*t-1);
            break;
        }
		else{
            /*更新*/
        }
    }
    /*输出答案*/
	i_ak ioi;
}

复杂度：

  • 时间复杂度： O(\frac{N}{K})
  • 空间复杂度： O(1)
3 个赞