借此把數(shù)形結合相關的知識補充補充，戳這里→淺談數(shù)形結合思想在信息學競賽中的應用

emmmmm求區(qū)間斜率最大的問題，用單調(diào)隊列去維護下凸曲線，感覺有些博客解釋的蠻清楚的，比如這里→戳

注意一下：下標的問題，還有，不要忘記初始化ansl,ansr

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX=1e5+5; int n,L,t,ansl,ansr; double ans=0; int pre_sum[MAX]; int st[MAX]; string s; double k(int l,int r) {return (double)(pre_sum[r]-pre_sum[l-1])/(double)(r-l+1); } int main() {cin>>t;while(t--){cin>>n>>L;cin>>s;pre_sum[0]=0;ans=0;ansl=1;ansr=n;for(int i=1;i<=n;i++){if(s[i-1]=='1')pre_sum[i]=pre_sum[i-1]+1;else pre_sum[i]=pre_sum[i-1];}int l=0,r=0;for(int i=L;i<=n;i++){while(l<r-1&&k(st[r-1],i-L)<k(st[r-2],i-L)) r--;st[r++]=i-L+1;while(l<r-1&&k(st[l],i)<=k(st[l+1],i)) l++;double temp=k(st[l],i);if(ans<temp||temp==ans&&i-st[l]<ansr-ansl){ansr=i;ansl=st[l];ans=temp;}}cout<<ansl<<" "<<ansr<<endl;}return 0;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/Egoist-/p/8177760.html

總結

以上是生活随笔為你收集整理的UVA 1451 Average 数形结合的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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