Lutece Problem 95-Ants Run

题目

https://acm.uestc.edu.cn/problem/ants-run/description
输入n和r分别代表蚂蚁只数和圆周半径，再输入n只蚂蚁的爬行速度。题目描述将n只蚂蚁按输入顺序以时钟顺序放在半径为r的的圆周上，当任一蚂蚁追上它前面的蚂蚁，游戏结束，要求找出最长的游戏时间（摆放位置不同，游戏时间也不同）。

分析

只要有一只蚂蚁追上其前面的蚂蚁游戏就结束，贪心策略告诉我们（，所有那些能追上前一只蚂蚁的蚂蚁（因为速度比前一只慢就追不上），同时追上时，游戏时间是最长的。于是转化为将两只相邻蚂蚁的速度差放置在圆周上的问题，下图举了两个半径均为1的例子。最终游戏时间就是1/k*圆周长，圆被等分成k份。

注意不要忘记第n-1和第0只蚂蚁也在发生追击。

程序

#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;
#define pi 3.141592653589793

int main()
{
    int cs;cin>>cs;
    int n, r;
    float spd[25], sub_spd[25];
    for(int T=0;T<cs;T++){
        cin >> n>> r;
        float l = 2*pi*r;
        cin >> spd[0];
        int spd_sum=0;
        for(int i=1;i<n;i++) {
            cin>>spd[i];
            spd[i]<spd[i-1]? sub_spd[i-1]=spd[i-1]-spd[i]:sub_spd[i-1]=0;
        }
        spd[n-1]>spd[0]?sub_spd[n-1]=spd[n-1]-spd[0]:sub_spd[n-1]=0;
        for(int i=0;i<n;i++)    spd_sum+=sub_spd[i];
        if(spd_sum==0) cout<<"Inf";
        else cout << setprecision(3)<<std::fixed<<l/spd_sum;
        if(T<cs-1) cout << "\n";
    }
    return 0;
}