原題

Description

　　動物園內最受歡迎就是猴子了，因為它們除了能爬能跳外還會很多技能。其中A類猴子特別擅長爬樹摘桃，而B類猴子擅長把桃子掰成兩半。
　　A類猴子有N只,編號為1到N，B類猴子有M只，編號為1到M。A類猴子中的第K只摘到第一個桃子需要花費A_k秒，此后每B_k秒就能摘到桃子；B類猴子中的第K只掰開第一個桃子需要花費C_k秒，此后每D_k秒就能掰開一個桃子。
　　不幸的是，B類猴子非常具有侵略性，兩種猴子不能同時待在場地內，因此，園長必須在A類猴子摘完所有桃子后立刻把它們帶走，然后立刻讓B類猴子進園；同樣當B類猴子把所有桃子全部掰開后也不能待在場地內太久，因為它們之間也會發生沖突，所有園長將在B類猴子掰開所有桃子后立刻送走它們。
　　園長帶走猴子和猴子進園的速度非常快，時間忽略不計。
　　Alice非常喜歡看B類猴子掰桃子，告訴你表演的總時間，但不知道一共有多少個桃子，請你幫Alice計算B類猴子進入動物園的時刻。

Input

　　輸入文件第一行包含一個整數T(1<=T<=1000000000)，表示猴子表演的總時間。
　　接下來一行包含一個整數N(1<=N<=100)，表示A類猴子的數量。
　　接下來N行，每行包含兩個整數A_k和B_k（1<=A_k,B_k<=1000000000），描述A類每只猴子摘桃的速度。
　　接下來一行包含一個整數M(1<=M<=100)，表示B類猴子的數量。
　　接下來M行，每行包含兩個整數C_k和D_k(1<=C_k,D_k<=1000000000)，描述B類每只猴子掰桃的速度。

Output

　　輸出兩類猴子進園的時刻相差多少秒。

Sample Input

輸入1：

12

1

3 1

1

5 1

輸入2：

20

2

3 2

1 3

3

3 1

4 1

5 1

Sample Output

輸出1：

5

輸出2：

13

Data Constraint

1≤T,Ak,Bk,Ck,Dk≤109

1≤N,M≤100

Hint

【樣例說明】
　　樣例1中，樹上有3個桃子：
　　(1) A類猴子在3秒時摘下第一個桃子，在4秒時摘下第二個桃子，在5秒時摘下第三個桃子；
　　(2) 在第5秒，園長把A類猴子帶走，此時B類猴子進園；
　　(3) B類猴子在10秒時掰開第一個桃子，在11秒時掰開第二個桃子，在第12秒時掰開第三個桃子；
　　(4) 在12秒時園長進園帶走B類猴子。

題解

• 兩猴相聚時間 T1 相當于A猴摘桃子的時間。

• 而B猴掰桃子的時間 T2 就等于總時間 T 減去 T1。

• 于是我們可以二分T1，O(n) 算出桃子數，接著判斷即可。

• 但由于AB猴兩邊所需時間不一定相等，最后應特判，能減則減。

Code

#include<cstdio> using namespace std; int a[101],b[101],c[101],d[101]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; }//讀入優化 int main() {int t=read(),n=read();for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();int m=read();for(int i=1;i<=m;i++) c[i]=read(),d[i]=read();int l=1,r=t;while(l<r){int mid=(l+r)/2,num=0;for(int i=1;i<=n;i++)if(mid>=a[i]) num+=(mid-a[i])/b[i]+1; for(int i=1;i<=m;i++)if(t-mid>=c[i]) num-=(t-mid-c[i])/d[i]+1;if(num>=0) r=mid; else l=mid+1;}//二分int num=0;for(int i=1;i<=n;i++)if(l>=a[i]) num+=(l-a[i])/b[i]+1; for(int i=1;i<=m;i++)if(t-l>=c[i]) num-=(t-l-c[i])/d[i]+1;if(num>0) l--;//檢驗printf("%d",l);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 1422. 猴子摘桃的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。