AcWing 2040. 礼物
原题链接
简单
作者:
BLOODHOUND
,
2022-05-04 14:26:35
,
所有人可见
,
阅读 176
(贪心) $O(nlogn)$
先按照总和排序,然后把能买的都买了
然后分两种情况:
1.记录一下能买的中价格最大的。把优惠券用在它身上,就会有多余的钱,再判断是否还能买之前买不起的
2.将优惠券花在买不起的物品身上,看看是否买得起
java 代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int m = s.nextInt();
List<int[]> list = new ArrayList<>();
for(int i=0;i<n;i++){
int p = s.nextInt();
int su = s.nextInt();
list.add(new int[]{p,su});
}
Collections.sort(list,(o1, o2) -> (o1[0]+o1[1])-(o2[0]+o2[1]));
int max = 0,cnt = 0;
int idx = 0;
for(;idx<n;idx++){
int p = list.get(idx)[0];
int su = list.get(idx)[1];
if(m>=p+su) {
m -= p + su;
cnt++;
max = Math.max(p, max);
}else break;
}
int t = m,c1 = 0,k = idx;
t+=max/2;
for(;k<n;k++){
int p = list.get(k)[0];
int su = list.get(k)[1];
if(t>=p+su) {
t -= p + su;
c1++;
}
}
t = m;k = idx;
for(;k<n;k++){
int p = list.get(k)[0];
int su = list.get(k)[1];
if(t>=p/2+su){
c1=Math.max(c1,1);
break;
}
}
System.out.println(cnt+c1);
}
}