質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1283閲覧

aoj alds search allocation

tokutok

総合スコア17

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2018/11/24 08:42

問題
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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

自己解決

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 b = right; c = left; 32 if (v <= k) right = mid; 33 else left = mid; 34 cout << left << " " << mid << " " << right << endl; 35 cout << c << " " << a << " " << b << endl; 36 if (a == mid && b == right && c == left) break; 37 } 38 return right; 39} 40int main() { 41 cin >> n >> k; 42 int Max = 0; 43 for (int i = 0; i < n; i++) { 44 cin >> w[i]; 45 Max = (w[i] > Max) ? w[i] : Max; 46 } 47 cout << binaryP(Max) << endl; 48 return 0; 49} 50

投稿2018/11/24 10:20

tokutok

総合スコア17

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問