← 전체 글로 돌아가기
competitive-programming2021년 1월 30일1분 분량

[Codeforces] 1475D. Cleaning the Phone 풀이

수정일: 2021년 12월 31일

Two pointersSortingsMeet in the middle
지원 언어:enko

#Problem

1475D. Cleaning the Phone

#Approach

이 문제는 "Two pointers" 문제입니다.

먼저 편의 점수를 기준으로 aia_i를 두 개의 배열로 나누고, 각각을 내림차순으로 정렬합니다.
이 배열들을 각각 one과 two라고 부르겠습니다.

figure.1
figure.1

one에서 l개의 앱을, two에서 r개의 앱을 선택한다고 합시다.
시작은 다음과 같습니다.

  • l= 0
  • r= two.size()

이미 삭제하기로 결정한 앱(r개)을 제외할 때는, 크기가 작은 앱부터 탐욕적으로 선택합니다.
반대로 새로운 앱을 추가할 때는 크기가 큰 앱부터 선택합니다.

처음에는 메모리의 합이 각각 sum1 = 0, sum2 = 6입니다.

figure.2
figure.2

이제 l = 0, 1, ... one.size()에 대해 다음을 반복합니다:

  1. sum1+sum2>=msum1 + sum2 >= m이 만족될 때까지 sum2=sum2−two[r−1]sum2 = sum2 - two[r-1]를 수행하고 r을 감소시킵니다.
  2. answer = min(answer, l + 2*r)
  3. sum1=sum1+one[l]sum1 = sum1 + one[l]
figure.3
figure.3
figure.4
figure.4
figure.5
figure.5

정렬에 O(nlog⁡n)O(n\log{n})이, 순회에 O(n)O(n)이 걸립니다.

#Code

/**
 * written: 2022-03-17 20:26:37 Thu [KST]
 * @jooncco's mac.
 **/
#include <bits/stdc++.h>
using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define f first
#define s second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef deque<int> di;
typedef deque<ll> dl;
typedef priority_queue<int, vi, less<int> > maxHeap;
typedef priority_queue<int, vi, greater<int> > minHeap;

const ll INF= 1e16;

int n,m;

void solve() {
    cin >> n >> m;
    vi arr(n);
    for (int &mem : arr) cin >> mem;
    vi one, two;
    int conv;
    for (int i=0; i < n; ++i) {
        cin >> conv;
        if (conv == 1) one.push_back(arr[i]);
        if (conv == 2) two.push_back(arr[i]);
    }
    sort(one.rbegin(), one.rend());
    sort(two.rbegin(), two.rend());

    ll ans= INF;
    ll sum1= 0, sum2= accumulate(two.begin(), two.end(), 0ll);
    int r= two.size();
    for (int l=0; l <= one.size(); ++l) {
        while (r > 0 && sum1 + sum2 - two[r-1] >= m) {
            sum2 -= two[--r];
        }
        if (r > -1 && sum1 + sum2 >= m) ans= min(ans, l+2ll*r);
        if (l < one.size()) sum1 += one[l];
    }

    cout << (ans == INF ? -1 : ans) << "\n";
}

int main() {
    FAST_IO;
    int t; cin >> t;
    while (t--) solve();
}

#Complexity

  • Time: O(nlog⁡n+n)O(n\log{n} + n)
  • Space: O(n)O(n)