AtCoder Beginner Contest 223 C - Doukasen
問題の要約
N本の導火線を一直線に接着したものがある。
左からi本目の導火線の長さはAicmで,1秒当たりBicmの一定の速度で燃える。
この導火線の左端と右端から同時に火をつけるとき,2つの火がぶつかる場所が着火前の導火線の左端から何cmの地点か求めよ。
制約
1<=N<=10^5
1<=Ai,Bi<=1000
入力
N
A1 B1
A2 B2
.
.
.
AN BN
出力
想定解答との絶対誤差または相対誤差が10^-5以下であれば正解として扱われる。
考え方
1,左から導火線に番号をつける。
0<=Ai,Bi<=N-1
2,まず両端から火をつけたとき導火線が全て燃える秒数を求め,左端から火を付けその秒数分だけ火が燃えた導火線の距離を求める。
3,両端から火をつけたとき導火線が全て燃える秒数を求める。
これはΣ(Ai/Bi)を2で割って求まる。これをsecとする。
4,左端から火をつけ,sec秒だけ燃やした時の距離を求める。
距離を0で初期化する。
左端つまりi=0からAi/Bi秒だけ燃えるので,Ai/Bi<=secならば距離にAiを足してsecからAi/Biを引く。
Ai/Bi>secならばBi*secを距離に足す。
実際のプログラム
#include<iostream>
#include<vector>
#include<map>
#include<iomanip>
using namespace std;
int main(){
long long N;
cin >> N;
vector<pair<double, double>> AB(N);
for(long long i = 0; i < N; i++){
cin >> AB[i].first >> AB[i].second;
}
double sec = 0;
for(long long i = 0; i < N; i++){
sec += AB[i].first/AB[i].second;
}
sec /= 2.;
double distance = 0.;
for(long long i = 0; i < N; i++){
if(AB[i].first/AB[i].second <= sec){
distance += AB[i].first;
sec -= AB[i].first/AB[i].second;
}else{
distance += AB[i].second*sec;
break;
}
}
cout <<setprecision(10)<< distance << endl;
return 0;
}