Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
放爷的算法,苯渣渣写的有砟代妈,一遍过了~膜拜放爷qaq//============================================================================ // 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; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator