問題
aoj alds allocation
上の問題に対して下のコードを書いてみました。
binaryP関数で終了条件がうまくいかないのですが、どうしたら良いでしょうか。
c++
1#include<iostream> 2using namespace std; 3 4const int N = 100001; 5const long long Pmax = 10000 * N; 6int w[N]; 7int n, k; 8 9int check(int mid) { 10 int tmp = 0, cnt = 1; 11 for (int i = 0; i < n; i++) { 12 if (tmp + w[i] > mid) { 13 tmp = w[i]; 14 cnt++; 15 } else { 16 tmp += w[i]; 17 } 18 } 19 return cnt; 20} 21int binaryP (int Max) { 22 int left = Max; 23 int right = Pmax; 24 int mid; 25 int a = (left + right) / 2, b = right, c = left; 26 while (right - left > 0) { 27 a = mid; 28 mid = (left + right) / 2; 29 int v = check(mid); //最大積載量P = mid のとき何台 30 cout<< "v = " << v << endl; 31 if (v <= k) { 32 b = right; 33 right = mid; //狭めていこう 34 } 35 else { 36 c = left; 37 left = mid; 38 } 39 cout << left << " " << mid << " " << right << endl; 40 cout << a << " " << b << " " << c << endl; 41 if (a == mid && b == right && c == left) break; 42 } 43 return mid; 44} 45int main() { 46 cin >> n >> k; 47 int Max = 0; 48 for (int i = 0; i < n; i++) { 49 cin >> w[i]; 50 Max = (w[i] > Max) ? w[i] : Max; 51 } 52 cout << binaryP(Max) << endl; 53 return 0; 54} 55
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。