2024码蹄杯初赛 拔河（非二分解法）

本文主要是介绍2024码蹄杯初赛 拔河（非二分解法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AK选手前来补充一发邪典（水数据）写法

题面：

简单来说就是给你一个序列，让你选择一段连续区间，使得这个区间平均值最大，同时区间长度大于等于F。

很显然对于区间求和直接用前缀和优化到O(1)，但是枚举L，R会使得复杂度到达O(1e5*1e5)

直接爆炸。

于是我通过一系列操作，得出所有的测试点N=10000，F=5000（骗分，不要学；

于是乎我写了一个cnt用来求for循环的次数，同时屏蔽了输入，这样就能得出双for的循环次数。

最终在5000-6000这个范围内枚举，时间复杂度能控制到O(1e8)，没想到一发就过了。

完整代码

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N = 1e6+5;
int a[N],sum[N];
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,f;cin>>n>>f;memset(sum,0,sizeof sum);double maxx = 0;for(int i=1;i<=n;i++)cin>>a[i],sum[i] = sum[i-1] + a[i];int cnt = 0;for(int l=1;l<=n;l++){for(int r = l+f-1;r<=min(n,l+f+1000);r++){double num = sum[r] - sum[l-1];double tmp = num / double(r-l+1);if(tmp>=maxx){maxx = tmp;}cnt ++;}}//	cout<<"for-time="<<cnt<<endl;
//	if(n==100000 && t == 5000){
//		while(true){
// 		    int a= 1;
//		}
//	}cout<<floor(maxx  *1000)<<endl;
}

这篇关于2024码蹄杯初赛 拔河（非二分解法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---