1494: 連續(xù)子串和續(xù)

http://www.acmore.net/problem.php?id=1494

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?99??Solved:?18
Submit Status Web Board

Description

?

小Y要去參加一場筆試，這場筆試有N道題目，每道題目有不同的分值和難度，分別為ai和bi。小Y想知道從某一題開始，至少連續(xù)K道題目，分值的和與難度的和的比率最大是多少？

?

?

Input

?

若干組測試數(shù)據(jù)，每組測試數(shù)據(jù)占3行。

第一行輸出兩個正整數(shù)N（1<=N<=10^6），K（1<=K<=N）。

第二行N個正整數(shù)a1,a2...aN表示N道題目的分值，其中（1<=ai<=1000）。

第三行N個正整數(shù)b1,b2...bN表示N道題目的難度，其中（1<=bi<=1000）。

?

?

Output

?

每組測試數(shù)據(jù)輸出一個實數(shù)，表示滿足題意的最大的比率，精確到小數(shù)點后4位。

?

Sample Input

?

5 3 1 2 3 4 5 1 1 3 4 5 3 1 100 200 300 3 2 1

?

Sample Output

?

1.2000 300.0000

?

HINT

?

?

Source

?

Lyush

?

設(shè)一個比例參數(shù)p，然后就是解決一個ai-p*bi的序列，至少連續(xù)K個，sum{ ai-p*bi } >= 0的問題了，二分枚舉這個參數(shù)即可

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 6 using namespace std; 7 8 #define eps 1e-8 9 10 const int INF=0x3f3f3f3f; 11 const int maxn=1000010; 12 13 int n,k; 14 int a[maxn],b[maxn]; 15 double num[maxn]; 16 17 int AC(double p){ 18 double tmp=INF; 19 num[0]=0; 20 for(int i=1;i<=n;i++) 21 num[i]=num[i-1]+a[i]-p*b[i]; 22 for(int i=k;i<=n;i++){ 23 tmp=min(tmp,num[i-k]); 24 if(num[i]-tmp>=0) 25 return 1; 26 } 27 return 0; 28 } 29 30 double BinSearch(double l,double r){ 31 double mid,ans; 32 while(r-l>eps){ 33 mid=(l+r)/2; 34 if(AC(mid)){ 35 ans=mid; 36 l=mid+eps; 37 }else 38 r=mid-eps; 39 } 40 return ans; 41 } 42 43 int main(){ 44 45 //freopen("input.txt","r",stdin); 46 47 while(~scanf("%d%d",&n,&k)){ 48 for(int i=1;i<=n;i++) 49 scanf("%d",&a[i]); 50 for(int i=1;i<=n;i++) 51 scanf("%d",&b[i]); 52 printf("%.4lf\n",BinSearch(0,1000)); 53 } 54 return 0; 55 }

?

總結(jié)

以上是生活随笔為你收集整理的1494: 连续子串和续的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。