BOJ1654:Lansun Cutting-C++
ローカルエリアネットワークのクリップ
コード#コード# #include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll N,M,high;
vector<ll> arr;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
{
int a;
cin >> a;
arr.push_back(a);
high=max(high,arr[i]);
}
/* left가 0이면 N=1,K=1, input=1 일 때 나누는 수인 mid가 0이되어서
런타임 에러가 발생한다 */
ll left=1, right=high;
ll ans=0;
while(left<=right)
{
ll tot = 0;
ll mid = (left + right)/2;
for(auto a : arr)
tot += a/mid; // 항상 mid가 0이되는 예외가 없는지 확인해줘야 함
if(tot < M)
right = mid - 1;
else
/* tot이 M보다 크거나 같을때 일단 지금까지 랜선 길이를 저장하고
더 큰값을 검사하러 이동 */
{
ans = max(ans,mid);
left = mid + 1;
}
}
cout << ans;
return 0;
}
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll N,M,high;
vector<ll> arr;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
{
int a;
cin >> a;
arr.push_back(a);
high=max(high,arr[i]);
}
/* left가 0이면 N=1,K=1, input=1 일 때 나누는 수인 mid가 0이되어서
런타임 에러가 발생한다 */
ll left=1, right=high;
ll ans=0;
while(left<=right)
{
ll tot = 0;
ll mid = (left + right)/2;
for(auto a : arr)
tot += a/mid; // 항상 mid가 0이되는 예외가 없는지 확인해줘야 함
if(tot < M)
right = mid - 1;
else
/* tot이 M보다 크거나 같을때 일단 지금까지 랜선 길이를 저장하고
더 큰값을 검사하러 이동 */
{
ans = max(ans,mid);
left = mid + 1;
}
}
cout << ans;
return 0;
}
:検索
최적의 랜선 길이
のナビゲーション이분탐색
:
이분탐색
をする時、よく나누는 수
人のmid
を探して0이되는 경우
を探して、예외처리
をします(本問題
:
N=1, M=1, input=1
の場合、mid
は0
であるため、최초left
を1
)Reference
この問題について(BOJ1654:Lansun Cutting-C++), 我々は、より多くの情報をここで見つけました https://velog.io/@neity16/BOJ-1654-랜선자르기-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol