//============================================================================
// Name        : main2018.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int pts[100001] = {0};
int state[100001] = {0};

int place;

int findMax(int wd, int start, int end){
	if(start == end) return start;
	int middle = (start + end)/2;
	double k1, k2, k;
	k = (pts[wd]+0.0-pts[state[middle]])/(wd-state[middle]);
	if(middle == 0) k1 = 0;
	else k1 = (pts[state[middle]] +0.0 - pts[state[middle-1]])/(state[middle] - state[middle-1]);
	if(middle == place-1) k2 = 1e10;
	else k2 = (pts[state[middle+1]] + 0.0 - pts[state[middle]])/(state[middle+1] - state[middle]);
	if(k >= k1 && k <= k2) return middle;
	else if(k > k1) return findMax(wd, middle+1, end);
	else return findMax(wd, start, middle-1);
}

int main() {
	int N, F;
	cin >> N >> F;

	place = 1;
	for(int i = 0; i < N; i++){
		int temp;
		cin >> temp;
		pts[i+1] = pts[i] + temp;
	}
	double mx = 0;
	for(int i = 0; i <= N-F; i++){
		int nwIdx = state[findMax(i+F, 0, place-1)];
		double nw = (pts[i+F]-pts[nwIdx]+0.0)/(i+F-nwIdx);
		if(mx < nw) {
			mx = nw;
			//cout << nwIdx << " " << i+F << endl;
		}

				//cout << i << " " << place << endl;
				//for(int j = 0; j < place; j++) cout << state[j] << " ";
				//cout << endl;

		if(i == N-F) break;
		int mIdx = findMax(i+1, 0, place-1);
		place = mIdx+2;
		state[place-1] = i+1;

	}
	cout << (int)(1000*mx) << endl;
	//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
	return 0;
}

• Re:放爷的算法，苯渣渣写的有砟代妈，一遍过了~膜拜放爷qaq (3) PvbeLLN 2025-02-23 15:56:09