100pts贪心求hack

反证法证明

假设存在序列 S 购买糖果数量 M > N。

步骤一：序列 S 必须包含所有 a_i < p_min 的糖果 如果序列 S 未购买某个 a_j < p_min 的糖果 j，则考虑序列 S 中一次花费 c ≥ p_min 的购买（这样的购买必存在，否则 S 仅购买 a_i < p_min 的糖果，则 M ≤ L，其中 L 为 a_i < p_min 的糖果数量，但方法中 N ≥ L，故 M ≤ N，矛盾）。

将这次花费 c 的购买替换为购买糖果 j 一次（花费 a_j < p_min ≤ c)，节省资金 c - a_j > 0。节省的资金可购买更多糖果，与 S 最优性矛盾。 因此，序列 S 必须包含所有 a_i < p_min 的糖果至少一次。

步骤二：比较剩余购买 设 L 为 a_i < p_min 的糖果数量。序列 S 和方法均先购买这些糖果，花费相同，剩余资金 m_L = m - ∑_{i∈L} a_i 。

在方法中，剩余资金 m_L 用于购买糖果 min 两次一组（每次花费 2 p_min ) 和可能的一次购买。设 t = ⌊ m_L / (2 p_min) ⌋，则方法购买 2 t 次糖果 min，花费 2 t p_min，剩余资金 r = m_L - 2 t p_min 。如果当前最小价格 ≤ r，则再购买一次，故方法剩余购买数 N - L = 2 t 或 2 t + 1.

在序列 S 中，剩余购买数为 M - L。 after L 购买后，所有糖果的当前价格至少为 p_min （因为对于非 L 糖果，a_i ≥ p_min ；对于 L 糖果，b_i > p_min ）。因此，每次购买花费至少 p_min ，故 M - L ≤ ⌊ m_L / p_min ⌋。

令 q = ⌊ m_L / (2 p_min) ⌋，则 m_L = 2 q p_min + r 其中 0 ≤ r < 2 p_min 。有： ⌊ m_L / p_min ⌋ = 2 q + ⌊ r / p_min ⌋ ≤ 2 q + 1（因为 r < 2 p_min )。

方法中 N - L = 2 q 或 2 q + 1.

若方法中 N - L = 2 q + 1，则 M - L ≤ 2 q + 1，故 M - L ≤ N - L，即 M ≤ N，矛盾。

若方法中 N - L = 2 q，则 M - L ≤ 2 q + 1。但 M > N 意味着 M - L > N - L = 2 q，故 M - L = 2 q + 1。此时，序列 S 有 2 q + 1 次购买，花费 m_L = 2 q p_min + r。但每次购买花费至少 p_min ，故总花费至少 (2 q + 1) p_min = 2 q p_min + p_min 。仅当 p_min ≤ r 时， 2 q p_min + p_min ≤ 2 q p_min + r = m_L 成立。但在方法中，如果 p_min ≤ r，则当前最小价格可能为 p_min ，方法应进行最后一次购买，即 N - L = 2 q + 1，与 N - L = 2 q 矛盾。因此，该情况不可能发生。

综上，假设 M > N 总导致矛盾，故方法能购买最多糖果。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1e5 + 5;
constexpr ll INF = (1ULL<<63)-1;
struct Candy{
    ll now, nxt; //这颗糖果现在的价格now和下一次价格nxt, 每买一次swap(now,nxt)
} c[N];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n,cur=0;
    ll m,minn=INF,cnt=0;
    cin>>n>>m;
    for(int i=0;i<n;++i){
        cin>>c[i].now>>c[i].nxt;
        minn=min(minn,c[i].now+c[i].nxt); //找到两个两个买“性价比”最高的糖果，但需考虑只买一个的情况
    }
    sort(c, c+n, [](Candy ca, Candy cb){
        if(ca.now != cb.now)
            return ca.now < cb.now;
        return ca.nxt < cb.nxt;
    });
    ll rem = m;
    for(cur=0;cur<n && c[cur].now*2<minn;++cur) { // c[cur].now*2 < minn 意味着只买一个比minn更优，因为minn是c[i].now+c[i].nxt
        rem-=c[cur].now;
        swap(c[cur].now,c[cur].nxt);
        cnt++;
    } //把只买一个的糖买完
    cnt+=rem/minn*2;
    rem=rem%minn; //两个两个买直到买不了两个成对（因为两个两个买不改变糖果的价格状态，即交换了偶数次，可以直接运算）
    for(int i=0;i<n;++i){
        if(c[i].now<=rem){
            rem-=c[i].now;
            cnt++;
            swap(c[i].now,c[i].nxt);
        }
    } //因为minn的第一个可能很大，所以要停下来再考虑能不能多买一个，若果能的话再+1. 注意当前minn+另外一个糖果可能多加两个
    cout<<cnt<<endl;
    return 0;
}