책 1 복사
https://www.acmicpc.net/problem/3487
3487호: 복사 서적
입력은 N개의 경우로 구성됩니다. 입력의 첫 번째 줄에는 양의 정수 N만 포함됩니다. 그런 다음 사례가 이어집니다. 각 케이스는 정확히 두 줄로 구성됩니다. 첫 번째 행에는 두 개의 정수 m과 k, 1 ≤ k ≤ m ≤ 500이 있습니다. 두 번째 행에는 li
www.acmicpc.net
(중골)정올 1156권 2권
출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=436&sca=40 Approach 이진 검색(2분 검색) 이진 검색(2분 검색) 이진 검색(2분 검색) Search) From Sorted Data 대상 값을 찾을 때 사용하는 탐색기
zoosso.tistory.com
https://howtoliveworldnice.429
백준 3487 책 베끼기
프레젠테이션 자료에 대한 Copying Book 2 문제는 파라메트릭 검색 솔루션을 강제로 복사하는 책에 M,K 범위를 추가하는 문제입니다. www.acmicpc.net/problem/3487 #3487: Copying books 입력은 N개의 경우로 구성됩니다. 첫번째
howtoliveworldnice.tistory.com
페이지 수가 결정되면 필요한 작가 수를 알 수 있습니다.
필요한 마커의 수는 가장 두꺼운 책의 페이지 수부터 순차적으로 계산되고 그 수가 k보다 작으면 그 수가 피치 기준이 됩니다.
공격
1. 프론트 직원을 적게 사용하기 때문에 뒤쪽에서 채웁니다.
2. 앞에서 1권도 배정받지 못한 직원이 있으면 앞에서 1권을 배정받는다.
#if 0
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
//ll book(511);
//ll N, K;
//
//int check(ll p)
//{
// ll sum = 0, cnt = 1;
// for (int i = 1; i <= N; i++)
// {
// sum += book(i);
// if (sum > p)
// {
// if (++cnt > K) return 0;
// sum = book(i);
// }
// }
// return 1;
//}
//int b_search(int s, int e)
//{
// if (s > e) return s;
// ll m = (s + e) / 2;
// if (check(m)) return b_search(s, m - 1);
// return b_search(m + 1, e);
//}
//void output(int ans)
//{
// ll i, sum = 0, cnt = 1, div(511) = { 0 };
// for (int i = N; i > 0; i--)
// {
// sum += book(i);
// if (sum > ans)
// {
// cnt++;
// sum = book(i);
// div(i) = 1;
// }
// }
// for (int i = 1; cnt < K; i++)
// {
// if (div(i) == 0)
// {
// div(i) = 1;
// cnt++;
// }
// }
// for (int i = 1; i <= N; i++)
// {
// printf("%d ", book(i));
// if (div(i) == 1) printf("/ ");
// }
// printf("\n");
//}
//int main(void)
//{
// freopen("input.txt", "r", stdin);
// ll T, low, high, ans;
// scanf("%d", &T);
// while (T--)
// {
// low = high = 0;
// scanf("%d %d", &N, &K);
// for (int i = 1; i <= N; i++)
// {
// scanf("%d", &book(i));
// high += book(i);
// if (low < book(i)) low = book(i);
// }
// ans = b_search(low, high);
// output(ans);
// }
//}
int TC;
int M;
int K;
bool check(int mid, vector<int> book)
{
ll cnt = 1;
ll sum = 0;
for (int i = 1; i <= M; i++)
{
sum += book(i);
if (sum > mid)
{
if(++cnt > K) return 0;
sum = book(i);
}
}
return (cnt <= K);
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("input.txt", "r", stdin);
cin >> TC;
while (TC--)
{
cin >> M >> K;
ll tmp;
ll low = 0;
ll high = 0;
ll ans = 0;
vector<int> book;
book.push_back(0);
for (int i = 1; i <= M; i++)
{
cin >> tmp;
book.push_back(tmp);
if (tmp > low) low = tmp;
high += tmp;
}
while (low <= high)
{
ll mid = (low + high) / 2;
if (check(mid, book))
{
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
ll sum = 0;
ll cnt = 1;
vector<int> div(510,0);
for (int i = M; i > 0; i--)
{
sum += book(i);
if (sum > ans)
{
cnt++;
sum = book(i);
div(i) = 1;
}
}
for (int i = 1; cnt < K; i++)
{
if (div(i) == 0)
{
div(i) = 1;
cnt++;
}
}
for (int i = 1; i <= M; i++)
{
cout << book(i) << ' ';
if (div(i) == 1) cout << "/ ";
}
cout << '\n';
}
return 0;
}
#endif
문제는 이런 식으로 백준에게 제출하면 절반만 성공한다는 점이다. 그 뒤에 있는 것은 잘못된 것으로 밝혀졌습니다.
그 이유는 백준님의 문제가 책정리2 형식이고, 기본적으로 10만 권의 책을 등록하여 시간이 흘렀기 때문입니다.
복사 책 2
#if 1
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
int TC;
int M;
int K;
ll low = 0, high = 0, ans = 0;
vector<int> book(100010);
bool check(ll mid)
{
ll cnt = 1;
ll sum = 0;
for (int i = 1; i <= M; i++)
{
sum += book(i);
if (sum > mid)
{
if (++cnt > K) return 0;
sum = book(i);
}
}
return (cnt <= K);
}
void output(int idx, ll sum, int ck)
{
if (idx < 1) return;
if (sum + book(idx) > ans || idx <= ck)
{
output(idx - 1, book(idx), ck - 1);
printf("%d / ", book(idx));
}
else {
output(idx - 1, sum + book(idx), ck);
printf("%d ", book(idx));
}
}
int main(void)
{
//freopen("input.txt", "r", stdin);
scanf("%d %d", &M, &K);
ans = 0;
low = high = 0;
for (int i = 1; i <= M; i++)
{
scanf("%d", &book(i));
if (book(i) > low) low = book(i);
high += book(i);
}
while (low <= high)
{
ll mid = (low + high) / 2;
if (check(mid))
{
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
output(M, 0, K-1);
return 0;
}
#endif