성공 입력 화면
문제
빵집
이제 집에서 성제앗당의 맛을 즐겨보세요!
소식을 접하지 못한 빵타쿠 한별은 곧바로 성재당으로 달려가 도시락을 샀다.
하지만 문제 해결에 여념이 없던 한별은 유통기한 내 식품을 먹는 것을 깜빡했다.
한별은 밀키트를 버리기 위해 눈물을 흘리며 포장을 뜯는 순간 재료마다 유통기한이 다르다는 사실을 발견했다.
쿡 세트 유통기한은 모든 재료 중 가장 빠른 날짜로 결정되기 때문에 아직 유통기한이 지나지 않은 재료들이 있었습니다.
푸드패키지에서 N 개 재료내가 포함 두 번째 재료의 만료일실버 디너 세트 구매 후 며칠까지, 감쇠율~이다 시 오전. 이때 구매 후 엑스 낮i번째 물질의 박테리아 수는 6 x 최대(1, x-Li) 마리 스텝입니다.
엑스 정수입니다.
모든 물질의 세균수 합계 G 이하어떤 경우에는 안전하게 먹을 수 있습니다.
밀키트를 너무 맛보고 싶은 한별이는 중요하지 않은 재료를 선택한다.
K에서 빼기 박테리아 수 G 1개 미만이면 그냥 먹기로 했어요.
한별이는 밀크킷을 며칠 후까지 먹을 수 있나요?
기입
첫 번째 줄에서 N, G, K는 공백으로 구분하여 지정됩니다.
두 번째 줄부터 개 시리즈에서 첫 번째 줄에 Decay rate, 이것은 두 번째 재료에 대한 정보입니다.
만료일 엘중요한 자료임을 나타내는 숫자 주어진 ~이다 0 또는 이다, 재료가 중요하지 않아 생략할 수 있음을 의미합니다.
누르다
중요하지 않은 항목을 최대한 활용하세요. 반려견을 꺼내면 사료를 구입한 후 몇 일 동안 먹을 수 있는지 출력합니다.
국경
1 ≤ n ≤ 200,000
1 ≤ g, Si, Li ≤ 10^9
0 ≤ k < n
접근하다
문제에 대한 이해
식사 세트에는 총 N개의 재료가 들어 있습니다.
그 아래 i번째 재료는 감쇠율(Si), 유통기한(Li), 중요재료 여부(Oi)의 3가지 조건이 부여된다.
1. 감쇠율
2. 유통기한 : 구매일로부터 1일
3. 재료 중요 여부 : Oi = 1이면 뺄 수 있는 재료(=비주요 재료)
구매 후 x일에 재료 i Si의 박테리아 수는 x max(1, x-Li)입니다.
모든 재료의 박테리아 수가 G 이하이면 먹습니다.
단, 위의 조건을 만족하더라도 필수불가결한 재료를 최대 K개까지 제외하여 먹습니다.
구매한 지 n일 후에 먹는다고 가정하고 n의 최대값을 찾으십시오.
입장
날짜그리고 적격 자료고려해야한다
하루 동안 제외할 자료의 우선 순위가 변경될 수 있습니다.
(재료마다 만료일수업 감쇠율은 다르다)
두 조건을 모두 고려하여 제외할 최대 K 재료를 구하는 절차는 다음과 같습니다.
1. 모든 박테리아의 합을 계산합니다.
-> Oi = 1인 재료의 박테리아 수는 새로운 배열에 저장됩니다.
2. Oi = 1인 재료의 박테리아 수를 저장하는 배열을 내림차순으로 정렬합니다.
3. 최대 K 물질에서 박테리아 수를 제외합니다.
-> 제외할 재료의 개수가 K보다 작으면 가능한 모든 재료를 제외한다.
연산
1. N 재료의 경우 모든 입력 값을 배열에 저장합니다.
2. 이진 검색
A. 과거 일자에 대한 모든 물질의 세균의 합을 계산한다.
– 이 방법에서는 Oi==1인 물질의 세균수를 벡터에 저장한다.
B. 벡터를 내림차순으로 정렬합니다.
(우선순위 = 세균 수)
C. 최대 K 물질의 박테리아 수를 제외합니다.
– 배제 가능한 물질의 개수는 K보다 작을 수 있으므로 min(k, vt.size())를 최대 범위로 한다.
시간적 복잡성
H = hi의 초기값 = 2*10^9 + 1
| 1000000001은 빡빡해서 더 높은 값을 지정해야 하는데 범위가 잘 모르겠습니다. -> 졸업 후 변경예정 |
이분 검색 – O(logH)
박테리아 수 – O(N)
정렬 – O(NlogN)
제외 재료 세균 추출 – O(N)
O(logH) * (2O(N) + O(NlogN)) → O(N로그N*로그H)
제출하다
40% 잘못된 → 좋아요!
!
1. 40% 재설정 → 높은 범위; 입력 Li X의 최대값!
!
더 많을 수 있습니다.
암호
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
ll g;
ll lo=0, hi=2000000001;
ll arr(200001)(3) = { 0 };
cin >> n >> g >> k;
for (int i = 0; i < n; i++) cin >> arr(i)(0) >> arr(i)(1) >> arr(i)(2);
ll ans=0;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
vector<ll> vt;
ll germ = 0;
for (int i = 0; i < n; i++){
ll temp = arr(i)(0) * max(1LL, mid - arr(i)(1));
germ += temp;
if(arr(i)(2) == 1) vt.push_back(temp);
}
sort(vt.begin(), vt.end(), greater<ll>());
for(int i = 0; i < min(k, int(vt.size())); i++) germ -= vt(i);
if(germ <= g) {
ans = max(ans, mid);
lo = mid + 1;
}
else hi = mid - 1;
}
cout << ans;
}
문제 포착
