Решение задачи Сжатие песен с Codeforces

Без пояснения   Просмотров: 103


У Ивана на телефоне есть n песен. Размер i-й песни ai байт. У Ивана также есть флеш-карта, которая может хранить не более m байт информации. Изначально его флеш-карта пустая.

Иван хочет записать все n песен на свою флеш-карту. Он может сжимать некоторые из них. Если он сжимает i-ю песню, размер i-й песни уменьшается с ai до bi байт (bi
Иван может сжать любое подмножество песен (возможно, пустое) и записать все песни на флеш-карту, если сумма их размеров не превышает m. Он может сжимать любое подмножество песен (не обязательно подряд идущих).

Иван хочет найти минимальное количество песен, которое необходимо сжать, чтобы все песни поместились на флеш-карте (то есть сумма их размеров была меньше либо равна m).

Если невозможно записать все песни (даже если Иван сожмет все песни, которые у него есть), выведите «-1». Иначе выведите минимальное количество песен, которое Ивану необходимо сжать.

Код

//song compression
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int long long  n, m, i = 0, sum = 0, count = 0;
	cin >> n >> m;
	vector<int long long  >v(n);
	while(n--)
	{
		int long long  a,b;
		cin >> a >> b;
		sum += a;
		v[i++] = a - b;
	}
	sort(v.begin(),v.end());
	i--;
	while(i >= 0 && sum > m){
	   sum -= v[i--];
	   count++;
    }
   if(sum <= m)
        cout << count << endl;
   else
        cout << -1 << endl;
   return 0;
}

         

Администратор Photo Автор: Администратор


Код

#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> a(n);
	long long sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i].first >> a[i].second;
		sum += a[i].first;
	}
	
	sort(a.begin(), a.end(), [&](pair<int, int> a, pair<int, int> b) { return a.first - a.second > b.first - b.second; });
	
	for (int i = 0; i < n; ++i) {
		if (sum <= m) {
			cout << i << endl;
			return 0;
		}
		sum -= a[i].first - a[i].second;
	}
	
	if (sum <= m)
		cout << n << endl;
	else
		cout << -1 << endl;
	
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться