CSES 정렬 및 검색 이것은 세 번째 질문입니다.
케이블카는 1인 또는 2인이 탑승할 수 있습니다.
문제는 모든 어린이를 태우는 데 필요한 최소한의 곤돌라를 인쇄하는 것입니다.
일
가지다 아니요 아이들은 관람차에 가고 싶어하고 당신의 임무는 각 아이들을 위한 곤돌라를 찾는 것입니다.
각 곤돌라에는 1명 또는 2명의 어린이가 탑승할 수 있으며 곤돌라의 총 중량은 다음을 초과할 수 없습니다.
엑스。 모든 어린이의 체중을 알고 있습니다.
어린이용 곤돌라의 최소 수는 얼마입니까?
입력하다
입력의 첫 번째 줄에는 두 개의 정수가 포함됩니다.
아니요 그리고 엑스: 어린이 수 및 최대 허용 체중.
다음 줄에는 다음이 포함됩니다.
아니요 정수 피하나,피2,…,피아니요: 각 어린이의 체중.
산출
정수를 인쇄하십시오: 곤돌라의 최소 수.
제한
- 하나≤아니요≤2⋅1e5
- 하나≤엑스≤1e9
- 하나≤피나≤엑스하나
예
입력하다:
4 10
7 2 3 9
산출:
삼
코드
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, x, ans;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> x;
vector<int> ar(n);
for (int i=0;i<n;i++) cin >> ar(i);
sort(ar.begin(), ar.end());
int l = 0, r = n - 1;
while (l <= r){
if (ar(l) + ar(r) <= x){
l++; r--;
}
else r--;
ans++;
}
cout << ans;
}무엇을 생각
- 정렬은 욕심 많은 방식으로 문제를 해결합니다.
- 가장 무거운 친구를 먼저 로드하고, 현재 탈 수 있는 경우 가장 가벼운 친구를 추가하고, 그렇지 않으면 추가하지 마십시오.
- 중간에서 두 번째 친구를 뽑을 수 있다면 그 친구를 뽑는 게 더 욕심이 날 것 같았는데 정렬된 배열의 비감소 특성을 감안할 때 한 번에 두 사람을 뽑을 수 있는 조건은 밖에 없다.
문제 — -> 매 2번부터 배열을 한 번 통과해야 하기 때문에 중개자를 찾는 효율이 높지 않다는 것을 알 수 있으며, 코드에 적힌 방법을 사용하더라도 최소한의 곤돌라를 얻을 수 있습니다.