問題描述 JiaoShou在愛琳大陸的旅行完畢，即將回家，為了紀念這次旅行，他決定帶回一些禮物給好朋友，
在走出了怪物森林以后，JiaoShou看到了排成一排的N個石子，
這些石子很漂亮，JiaoShou決定以此為禮物，
但是這N個石子被施加了一種特殊的魔法，
如果要取走石子，必須按照以下的規則去取，
每次必須取連續的2*K個石子，并且滿足前K個石子的重量和小于等于S，后K個石子的重量和小于等于S，
由于時間緊迫，Jiaoshou只能取一次，
現在JiaoShou找到了聰明的你，問他最多可以帶走多少個石子 樣列輸入 8 3
1 1 1 1 1 1 1 1 樣列輸出 6 樣列解釋 任意選擇連續的6個1即可， 思路：二分答案，每次二分一個答案，如果當前的答案能滿足存在一個序列S1+...+Sk<=s并且Sk+1+...+S2k<=s,就繼續從mid后面找，如果不滿足就從mid前面找，把滿足的結果保存下來，最后保存的結果就是要求的結果，時間復雜度為n(logn)，能跑完， AC代碼：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int Max=1000003; 5 const int mod=10007; 6 ll sum[Max]; 7 int n; 8 ll s; 9 int kk(int k) 10 { 11 for(int i=k; i<=n&&i+k<=n; i++) 12 if(sum[i]-sum[i-k]<=s&&sum[i+k]-sum[i]<=s)return 1;//存在序列i~i+2*k-1滿足條件 13 return 0; 14 } 15 int main() 16 { 17 18 cin>>n>>s; 19 for(int i=1; i<=n; i++) 20 { 21 ll a; 22 cin>>a; 23 sum[i]=sum[i-1]+a; 24 } 25 int k=0; 26 int l,r; 27 l=1; 28 r=n/2;//不能超過序列的一半 29 while(l<=r) 30 { 31 int mid=(l+r)/2; 32 if(kk(mid)) 33 { 34 l=mid+1; 35 k=mid; 36 } 37 else r=mid-1; 38 } 39 cout<<k*2<<endl; 40 }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412972.html
標籤：其他
上一篇：【Warrior刷題筆記】力扣306.累加數 【列舉+高精度加法】詳細注釋 雙超100
下一篇：HashMap原理及原始碼分析