백준 1680번 쓰레기 수거 C++

출처 : https://www.acmicpc.net/problem/1680

 

가까운 쓰레기장부터 방문하면서 실었는데 용량을 넘기거나 실었는데 용량이 가득 찼을 때 처음으로 되돌아가서 버리고 다시 온다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;
	while (t--) {
		int w, n;
		cin >> w >> n;
		vector<pair<int, int>> trash(n);
		for (int i = 0; i < n; i++) {
			int x_i, w_i;
			cin >> x_i >> w_i;
			trash[i] = make_pair(x_i, w_i);
		}
		int sum = 0;
		int curr_lot = 0;
		int curr_weight = 0;
		int idx = 0;
		while (idx < n) {
			if (curr_weight + trash[idx].second == w) {
				sum += trash[idx].first;
				curr_weight = 0;
				idx++;
				continue;
			}
			else if (curr_weight + trash[idx].second < w) {
				curr_weight += trash[idx].second;
				idx++;
				continue;
			}
			else {
				sum += trash[idx].first;
				curr_weight = 0;
			}
		}
		if (curr_weight > 0) {
			sum += trash[n - 1].first;
		}
		cout << sum * 2 << "\n";
	}
};