[알고스팟] 록 페스티벌 ID: FESTIVAL

문제 링크

이글을 검색하여 들어오신 분들은 알고리즘을 입문하시는 분들이라 생각됩니다.

이 블로그는 매일 푼 문제에 대하여 글을 올리고 있습니다. 주로 종만북과 백준을 이용합니다.

 

1, 2, 3 ... N 번째 중 i번째 날까지의 누적 합을 psum[i] 에 저장하면 O(1)의 복잡도로 [start: end] 구간 합 계산이 가능합니다. 예를 들어 3~6 번째 날의 구간 합은 psum[6] - psum[3-1] 으로 구할 수 있습니다.

간단한 아이디어지만 PS할 때 많이 사용됩니다.

 

 

/* 2019-06-22 */

#include <stdio.h>
#define min(a,b) (a<b?a:b)
int main() {
	int t;
	scanf("%d", &t);
	for (; t--;) {
		int n, l;
		scanf("%d %d", &n, &l);
		int psum[1001] = { 0, };
		int cost;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &cost);
			psum[i] = psum[i - 1] + cost;
		}
		double ans = 1000.0;
		for (int i = l; i <= n; i++) {
			int s = 1, e = i;
			while (e <= n) {
				double av = (double)(psum[e] - psum[s-1]) / i;
				s++, e++;
				ans = min(ans, av);
			}
		}
		printf("%0.9lf\n", ans);
	}
}