#23071 (C++11) No.198 キャンディー・ボックス２

• 問題: No.198 キャンディー・ボックス２
• ユーザー: 古寺いろは
• 提出日時: 2015-04-28 23:46:56
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 761 bytes
• コンパイル時間: 1,238 ms
• コンパイル使用メモリ: 159,324 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-07-05 05:09:02
• 合計ジャッジ時間: 1,888 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	WA	-
testcase_03	AC	1 ms; 6,940 KB
testcase_04	AC	1 ms; 6,944 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	AC	1 ms; 6,948 KB
testcase_08	WA	-
testcase_09	AC	1 ms; 6,940 KB
testcase_10	AC	2 ms; 6,940 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	1 ms; 6,940 KB
testcase_14	AC	1 ms; 6,944 KB
testcase_15	AC	1 ms; 6,940 KB
testcase_16	AC	2 ms; 6,944 KB
testcase_17	AC	2 ms; 6,944 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	2 ms; 6,940 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	AC	2 ms; 6,940 KB

ソースコード

#include "bits/stdc++.h"
using namespace std;

 
vector<int> C;
int B, N;
long long ans;

long long calc(int a){
	int nokori = B;
	long long temp = 0;
	for (int i = 0; i < N; i++)
	{
		temp += abs(a - C[i]);
		nokori += C[i] - a;
	}
	if (nokori < 0) return (long long) 1e18;
	ans = min(temp, ans);
	return temp;
}

int main() {
	cin >> B;
	cin >> N;
	C = vector<int>(N);
	for (int i = 0; i < N; i++)
	{
		cin >> C[i];
	}
	ans = (long long) 1e18;
	int low = 0;
	int high = (int)1e9;
	while (high - low > 10){
		int lowmid = (low + low + high) / 3;
		int highmid = (low + high + high) / 3;
		if (calc(lowmid) <= calc(highmid)) high = highmid;
		else low = lowmid;
	}

	for (int i = max(0 , low - 100); i < low + 100; i++)
	{
		calc(i);
	}
	cout << ans << endl;
}