백준 24508번 나도리팡 [C++]

https://www.acmicpc.net/problem/24508

 

 

#문제 간단 정리

투 포인터를 사용하자

 

#문제 해결 방법

 

일단 정렬을 해주게 되면

우측에는 나도리가 많고 좌측에는 적기때문에

 

조건문1)

우측에 나도리가 기준치보다 적다면 좌측의 나도리를 왼쪽의 나도리를 사용해서

채워주는게 유리 

 

조건문2)

우측의 나도리가 기준치보다 많고

좌측의 나도리가 기준치보다 적다면

당연히 좌측의 나도리를 사용해서 우측의 나도리를 기준치만큼 채워주면된다

 

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, t;
    cin >> n >> k >> t;

    vector<int> vec(n);

    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }

    sort(vec.begin(), vec.end());

    int left = 0;
    int right = vec.size()-1;
    long long count = 0;

         
    while (left < right) {
        

        if (vec[right] == k) {
            right--;
            if (left >= right) {
                break;
            }
        }
        else if (vec[right] < k) {

            int temp = k - vec[right];
            
            if (temp > vec[left]) {
                count += vec[left];   
                vec[right] += vec[left];
                vec[left] = 0;
                left++;
            }
            else if (temp < vec[left]) {
                vec[left] -= temp;
                vec[right] += temp;
                right--;
                count += temp;
            }
            else if (temp == vec[left]) { 
                vec[left] = 0;
                vec[right] += temp;
                left++;
                right--;
                count += temp;
            }
            
        }


        if(vec[left] < k && vec[right] > k) {

            int temp = k - vec[left];
            int temp2 = vec[right] - k;

            if (vec[right] - temp >= k) {
                vec[right] -= temp;
                vec[left] += temp;
                count += temp;
                left++;
            }
            else {
                vec[right] -= temp2;
                vec[left] += temp2;
                count += temp2;
                right--;
            }
    
        }
        else if (vec[left] == k || vec[left] == 0) {
            left++;
        }


    }



    for (auto a : vec) {
        if (a != k && a!=0) {
            cout << "NO" << '\n';
            return 0;
        }
    }
    if (count <= t) {
        ;
        cout << "YES" << '\n';
    }
    else {
        cout << "NO" << '\n';
    }
    return 0;
}