T1 糖果店

solution

首先容易注意到对于每个糖果，一下买两个花 $x + y$ 块钱。

我们可以把糖果按 $x$ 进行排序，依次枚举买前 $i$ 个糖果，买了之后还剩 $m - \sum_{k = 1}^i{x_k}$ 块钱，我们可以把这些钱全部用于买 $x + y$ 最小的糖果。

一个不严谨的证明：买糖果可以分为两种，一次买两个糖果和一次只买一个糖果，买两个显然只能买 $x + y$ 最小的糖果，所以我们只用先枚举买一个的情况，再将钱用于买两个的情况，所以上述贪心策略是不劣的。

目前通过了民间数据

时间复杂度：$O(n\log n)$

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
const int inf = 1e18;

struct node{
	int x , y;
}a[N];

int n , m , mi = inf , s , ans;

bool cmp(const node &lhs , const node &rhs){
	return lhs.x < rhs.x;
}

signed main(){
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i].x >> a[i].y;
		
		mi = min(mi , a[i].x + a[i].y);
	}
	
	sort(a + 1 , a + n + 1 , cmp);
	
	ans = m / mi * 2;
	for(int i = 1 ; i <= n ; i ++){
		s += a[i].x;
		if(s > m) break;   // 注意特判，考场上寄这里了qwq
		ans = max(ans , (m - s) / mi * 2 + i);
	}
	cout << ans;
	return 0;
}

后记

我打完这次 noip 后就 AFO 了，虽然这次也不出所料的考砸了。但是我想告诉广大的 oier 们，这只是一次考试，并不是我们 oi 生涯的全部，更不是我们无数次日日夜夜训练的全部。

愿我们都能在这次 noip 中取得自己想要的成绩，愿不论是要退役的 oier 还是继续坚持 oi 的 oier 我们都能在未来找到自己。

可不可以让我再 让我， 再一次回到那个美丽世界里， 找自己 --《找自己》 陶喆