글 읽기 - 8986번 전봇대 어떤 케이스에서 틀릴까요 ㅠㅠ?

20151571 6년 전 0

1시간 동안 안되는 케이스를 찾아봤는데도 모르겠네요...

제발 알려주세요 ㅠㅠ

#include <cstdio>

typedef long long ll;
const int N = 100000;
const ll INF = (ll)1e9;
ll a[N + 1];

ll abs(ll x) {
	return x > 0 ? x : -x;
}

int main() {
	int n;
	ll str = 1, last = 0, ans = INF * 2, sum, num;

	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%lld", a + i);
		if ( i > 0)
			last = last > (a[i] - a[i - 1]) ? last : (a[i] - a[i - 1]);
	}
	ans = last;
	while (str <= last) {
		ll mid = (str + last) / 2;
		sum = num = 0;
		for (ll i = 1; i < (ll)n; ++i) {
			num += (mid * i - (a[i] - a[0]));
			sum += abs(mid * i - (a[i] - a[0]));
		}
		if (num > 0ll)
			last = mid - 1;
		else
			str = mid + 1;
		if (ans > sum)
			ans = sum;
	}
	printf("%lld\n", ans);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

8986번 전봇대 어떤 케이스에서 틀릴까요 ㅠㅠ?

20151571 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말