CF1015C Songs Compression (#贪心)

题目描述

Ivan has nn songs on his phone. The size of the ii -th song is a_iai​ bytes. Ivan also has a flash drive which can hold at most mm bytes in total. Initially, his flash drive is empty.

Ivan wants to copy all nn songs to the flash drive. He can compress the songs. If he compresses the ii -th song, the size of the ii -th song reduces from a_iai​ to b_ibi​ bytes ( b_i < a_ibi​<ai​ ).

Ivan can compress any subset of the songs (possibly empty) and copy all the songs to his flash drive if the sum of their sizes is at most mm . He can compress any subset of the songs (not necessarily contiguous).

Ivan wants to find the minimum number of songs he needs to compress in such a way that all his songs fit on the drive (i.e. the sum of their sizes is less than or equal to mm ).

If it is impossible to copy all the songs (even if Ivan compresses all the songs), print "-1". Otherwise print the minimum number of songs Ivan needs to compress.

输入输出格式

输入格式：

 

The first line of the input contains two integers nn and mm ( 1 \le n \le 10^5, 1 \le m \le 10^91≤n≤105,1≤m≤109 ) — the number of the songs on Ivan's phone and the capacity of Ivan's flash drive.

The next nn lines contain two integers each: the ii -th line contains two integers a_iai​ and b_ibi​ ( 1 \le a_i, b_i \le 10^91≤ai​,bi​≤109, a_i > b_iai​>bi​ ) — the initial size of the ii -th song and the size of the ii -th song after compression.

 

输出格式：

 

If it is impossible to compress a subset of the songs in such a way that all songs fit on the flash drive, print "-1". Otherwise print the minimum number of the songs to compress.

 

输入输出样例

输入样例#1

4 21
10 8
7 4
3 1
5 4

输出样例#1

2

输入样例#2

4 16
10 8
7 4
3 1
5 4

输出样例#2

-1

说明

In the first example Ivan can compress the first and the third songs so after these moves the sum of sizes will be equal to 8 + 7 + 1 + 5 = 21 \le 218+7+1+5=21≤21 . Also Ivan can compress the first and the second songs, then the sum of sizes will be equal 8 + 4 + 3 + 5 = 20 \le 218+4+3+5=20≤21 . Note that compressing any single song is not sufficient to copy all the songs on the flash drive (for example, after compressing the second song the sum of sizes will be equal to 10 + 4 + 3 + 5 = 22 > 2110+4+3+5=22>21 ).

In the second example even if Ivan compresses all the songs the sum of sizes will be equal 8 + 4 + 1 + 4 = 17 > 168+4+1+4=17>16 .

---

思路

题目大意：有n首歌曲，给定压缩前和压缩后的大小，以及U盘的空间m。现在求最少压缩几首歌能把所有歌放入U盘，如果放不进去输出-1。

贪心，先写2个特判以便节省时间。

1.如果压缩后的全部歌曲$s2$大于m，则说明肯定放不进去，输出-1结束即可；

2.如果未压缩的全部歌曲s1小于等于m，则说明一定能全部放进去，输出0即可。

如果不符合上述情况，则把每个歌曲i**未压缩和压缩后的大小差**从大往小排序，因为我们要选尽可能少费空间（差值大的）的让最优解最优。然后**贪心**，差值大的优先放入U盘。

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct//歌曲结构体 
{
	long long int a,b,dc;//a和b分别是对于歌曲i来说，压缩前的空间和压缩后的空间，dc是它们的差值 
}lxydl;
lxydl song[100001];
long long int n,m,s1,s2,s,cnt;//注意要开long long 
inline int cmp(lxydl a,lxydl b)//按歌曲压缩空间差值从大往小排序 
{
	return a.dc>b.dc;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	register long long int i;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>song[i].a>>song[i].b;
		song[i].dc=song[i].a-song[i].b;//计算歌曲的空间差 
		s1=s1+song[i].a;//计算未压缩的歌曲空间总和 
		s2=s2+song[i].b;//计算压缩的歌曲空间总和
	}
	if(s2>m)//如果压缩后的歌曲还比m大 
	{
		cout<<-1<<endl;
		return 0;
	}
	if(s1<=m)//如果未压缩的歌曲比m小 
	{
		cout<<0<<endl;//肯定都能放进去，不用压缩 
		return 0;
	}
	sort(song+1,song+n+1,cmp);//排序 
	long long int space(s1-m);//计算空间差 
	for(i=1;i<=n;i++)
	{
		if(s>=space)//如果空间不够了 
		{
			break;
		}
		else
		{
			s=s+song[i].dc;
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}