[伯俊]2343ギターレッスン
白駿2343ギターレッスン
https://www.acmicpc.net/problem/2343
可能な限り短いBlu-rayの長さ:最長のコースの長さ
可能なBlu-ray最大長:コースの最大数87*∗コースの最大長=100000;87*8710000
https://www.acmicpc.net/problem/2343
可能な限り短いBlu-rayの長さ:最長のコースの長さ
可能なBlu-ray最大長:コースの最大数87*∗コースの最大長=100000;87*8710000
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
//최적화 문제: M개의 블루레이로 모든 레슨을 녹화할 수 있는 블루레이의 크기 중 최솟값을 구해라
//결정 문제: 크기 x 혹은 x이하인 블루레이 M개로 모든 레슨을 녹화할 수 있는가?
int n, m;
vector<int> lesson;
bool decision(double x) {
//모든 레슨을 녹화하기 위해 필요한 블루레이의 개수
int cnt = 1;
//하나의 블루레이에 들어갈 레슨의 길이의 합
int sum = 0;
for (int i = 0; i < n; ++i) {
if (sum + lesson[i] > x) {
cnt++;
sum = lesson[i];
}
else sum += lesson[i];
}
return cnt <= m;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
//가장 길이가 긴 레슨의 길이
int longestlesson = 0;
for (int i = 0; i < n; ++i) {
int input;
cin >> input;
lesson.push_back(input);
longestlesson = max(longestlesson, input);
}
double hi = 10000 * 100000;
double lo = longestlesson;
for (int it = 0; it < 100; ++it) {
double mid = (hi + lo) / 2;
if (decision(mid)) hi = mid;
else lo = mid;
}
cout << lo;
return 0;
}
Reference
この問題について([伯俊]2343ギターレッスン), 我々は、より多くの情報をここで見つけました https://velog.io/@sunjoo9912/백준-2343-기타-레슨テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol