Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse files

add 2018, convex, maximum average subsequence

  • Loading branch information...
commit 1bf7dc9f5a06f85d8e0aed61f279adafdfe883c5 1 parent c23aada
@brianchenming authored
Showing with 100,062 additions and 30 deletions.
  1. +49 −30 2018/fence.cpp
  2. +100,001 −0 2018/in
  3. +9 −0 2018/in2
  4. +3 −0  2018/in3
View
79 2018/fence.cpp
@@ -16,44 +16,63 @@
* =====================================================================================
*/
-#include <iostream>
+#include <stdio.h>
+#include <stdlib.h>
-using namespace std;
+const int MAXN = 100001;
int
main ( int argc, char *argv[] )
{
- int N, F;
+ int N, F, t, sum[MAXN] = {0};
- if ( cin >> N >> F ) {
- int fields[N];
- for ( int i=0; i<N; ++i ) {
- cin >> fields[i];
- }
+ if ( scanf("%d %d", &N, &F) != EOF ) {
+ for ( int i=1; i<=N; ++i ) {
+ scanf("%d", &t);
+ sum[i] = sum[i-1] + t;
+ }
+ if (N < 3) {
+ if (N == 1) {
+ printf("%d\n", 1000*sum[1]);
+ } else {
+ if (F == 1) {
+ int a = sum[1], b = sum[2] - sum[1];
+ printf("%d\n", 1000*(a > b ? a : b));
+ } else {
+ printf("%d\n", 1000*sum[2]/2);
+ }
+ }
+ return 0;
+ }
- int st, end, sum, len;
- double max_avg = 0.0;
- end = st = sum = len = 0;
- while ( len++ < F ) {
- sum += fields[end++];
- }
- max_avg = sum/len;
+ double bestavg = sum[F]/((double)F);
+ int bestbeg = 0, bestend = F;
- while ( st < end ) {
- sum += fields[++end];
- ++len;
-
-
- while ( fields[st]*len <= sum && len> F ) {
- sum -= fields[st++];
- --len;
- }
-
- if ( max_avg*len < sum ) {
- max_avg = sum/len;
- }
- }
-
+ // maintain a down-convex hull of check points
+ int chl = 0; // left boundary of the hull to check
+ for(int i=F+1; i<=N; ++i) {
+ int chr = i-F; // right boundary of the hull to check
+ double avg_r = (sum[i]-sum[chr])/(double)(i-chr);
+ double avg_l = (sum[i]-sum[chl])/(double)(i-chl);
+ if (avg_r > avg_l) {
+ // chr will no longer be a check point for the best answer
+ // then the hull to check shrink to a point
+ chl = chr;
+ if (avg_r > bestavg) {
+ bestavg = avg_r;
+ bestbeg = chr;
+ bestend = i;
+ }
+ } else {
+ // chr is an inner point of the hull, just ignore it
+ if (avg_l > bestavg) {
+ bestavg = avg_l;
+ bestbeg = chl;
+ bestend = i;
+ }
+ }
+ }
+ printf("%d\n", 1000*(sum[bestend] - sum[bestbeg])/(bestend - bestbeg));
}
return EXIT_SUCCESS;
View
100,001 2018/in
100,001 additions, 0 deletions not shown
View
9 2018/in2
@@ -0,0 +1,9 @@
+8 4
+1
+1
+1
+2
+1
+1
+1
+2
View
3  2018/in3
@@ -0,0 +1,3 @@
+2 2
+3
+4
Please sign in to comment.
Something went wrong with that request. Please try again.