ABC030_C
飛行機で何往復できるかという問題
普通にやると大変なのでlower_bound()による二分探索を使った.
lower_bound(a,a+n,value)はvalue以上の値の位置を返す.
#include <bits/stdc++.h> using namespace std; int main(){ int a[5] = {1,3,5,7,9}; int* pos = lower_bound(a,a+5,8);//8を初めて越すのはa[4]:9 cout<<pos-a<<endl;//4 cout<<*pos<<endl;//9 return 0; }
配列aの範囲内に有るか無いかを条件文で判断するには
if(pos-a<n)//ある else //ない
を用いた.
もっと良い方法がありそうだが…
解答
#include <bits/stdc++.h> using namespace std; int main() { int n,m,x,y; int a[100000],b[100000]; cin>>n>>m>>x>>y; for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<m;i++)cin>>b[i]; int cur = 0; int *pos; int res = 0; int flag = 1;//flag = 1ならばAにいる while(1){ if(flag){ pos = lower_bound(a,a+n,cur);//curより大きい最初の位置 if(pos-a<n){ cur = *pos+x;//飛行機に乗る flag = 0; }else{ break; } }else{ pos = lower_bound(b,b+m,cur); if(pos-b<m){ cur = *pos+y; res++; flag = 1; }else{ break; } } } cout<<res<<endl; return 0; }