백준 25947번: 선물할인

선물할인
실버라서 쉬울줄 알았는데 너무 어려웠다.
최종적으로 a개를 할인받아 총 n개를 예산 b에 딱 맞게 샀다면,
n개 중 할인받은 a개들이 가장 비싼 놈들이라는걸 생각을 못해냈다.
실버 문제들 많이 풀어봐야겠다...
 

#include <bits/stdc++.h>

#define FOR(i, n) for(int i = 0; i < int(n); i++)
#define FORL(e, s) for(auto &e : s)
#define endl "\n"
#define vi vector<int>

using namespace std;

int N, budgets, coupons;

struct Price {
    int p = 0;
    bool is_c = false;
    void set_c(bool b = true) { is_c = b; }
    int get_p() { return p / (is_c ? 2 : 1); }
    Price(int price) { p = price; }
};
bool cmp(Price& p1, Price& p2) { return p1.get_p() < p2.get_p(); }
vector<Price> vp;

int main() {
    cin >> N >> budgets >> coupons;
    FOR(i, N) { int tmp; cin >> tmp; vp.emplace_back(tmp); }
    sort(vp.begin(), vp.end(), cmp);

    int piv = 0;
    long long sum = 0;

    for (int i = 0; i < coupons; i++) {
        vp[i].set_c();
        if (sum + vp[i].get_p() <= budgets) { sum += vp[i].get_p(); }
        else { cout << i << endl; return 0; }
    }

    int wsize = coupons;
    while (piv + wsize < N) {
        sum -= vp[piv].get_p();
        vp[piv].set_c(false);
        sum += vp[piv].get_p();

        vp[piv + wsize].set_c(coupons != 0);
        sum += vp[piv + wsize].get_p();

        if (sum <= budgets) { piv += 1; }
        else { break; }
    }

    cout << piv + wsize << endl;
    return 0;
}