Codeforces Round #790 (Div. 4) - E

문제 출처:

https://codeforces.com/contest/1676/problem/E

 

문제 분석:

설탕의 양이 주어져있고 쿼리로 현재 설탕으로 쿼리값을 만들려면 최소 몇개의 설탕이 필요한지를 알아야한다.

그래서 처음에는 브루트포스로 가능할줄알았지만 쿼리의 양이 매우 많아 시간초과가 난다.

따라서 이분탐색을 이용해서 문제를 해결했다.

 

문제 해결:

설탕을 정렬한 다음 뒤집어서 부분합을 만들어 놓는다.

그리고 lowerbound로 값을 찾으면 최소 개수 및 가능한지 여부를 확인 할 수 있다.

 

내 소스코드:

// freopen("input.txt", "r", stdin);
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cstring>
#include <list>
#include <set>
#include <string.h>
#include <map>
#include <limits.h>
#include <stdlib.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int INF = 987654321;
int testcase;

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

	cin >> testcase;

	while (testcase--)
	{
		int n, q;
		cin >> n >> q;

		vector<int> v;
		int sum = 0;
		vi psum;

		rep(i, n)
		{
			int tmp;
			cin >> tmp;
			v.push_back(tmp);
			sum += tmp;
		}
		sort(v.begin(), v.end(), greater<int>());
		int cur = 0;
		psum.resize(n);
		rep(i, n)
		{
			cur += v[i];
			psum[i] = cur;
		}

		rep(i, q)
		{
			int tmp;
			cin >> tmp;

			if (tmp > sum)
			{
				cout << "-1\n";
				continue;
			}

			auto it = lower_bound(psum.begin(), psum.end(), tmp);
			int ans = it - psum.begin() + 1;
			cout << ans << "\n";
		}
	}

	return 0;
}

 

고찰:

F번 문제를 잘못 이해해서 여러번 잘못풀어서 시간이없었다.

시간만 있었으면 풀 수 있었을텐데..