題目
https://acm.uestc.edu.cn/problem/ants-run/description
輸入n和r分別代表螞蟻只數(shù)和圓周半徑糊识，再輸入n只螞蟻的爬行速度譬淳。題目描述將n只螞蟻按輸入順序以時鐘順序放在半徑為r的的圓周上蚯舱，當任一螞蟻追上它前面的螞蟻璃搜，游戲結(jié)束，要求找出最長的游戲時間（擺放位置不同喜爷，游戲時間也不同）丐箩。
分析
只要有一只螞蟻追上其前面的螞蟻游戲就結(jié)束晋控，貪心策略告訴我們（，所有那些能追上前一只螞蟻的螞蟻（因為速度比前一只慢就追不上）茫虽，同時追上時刊苍，游戲時間是最長的。于是轉(zhuǎn)化為將兩只相鄰螞蟻的速度差放置在圓周上的問題濒析，下圖舉了兩個半徑均為1的例子班缰。最終游戲時間就是1/k*圓周長，圓被等分成k份悼枢。
用速度差平分圓周
注意不要忘記第n-1和第0只螞蟻也在發(fā)生追擊埠忘。
程序
#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;
}
