鸡很饿,鸡要吃外卖,今天点份炸鸡外卖!鸡使用的外卖程序有若干个满减优惠,第 i个优惠可以表示为"满 ai 元减 bi 元",多个满减优惠可以叠加。满减的具体结算流程是:假设鸡购买的食物原价共为 x 元,则所有满足 x ≥ ai 的满减优惠都可以一起同时被使用,优惠后价格记为 y,则鸡只要支付 y 元就可以了(若 y ≤ 0则不需要支付)。现在,鸡的手机里一共只有 m 元钱,鸡想知道,他所购买的食物原价 x 最多为多少。

输入格式

输入第一行包括一个整数 T(1 ≤ T ≤ 10^4),样例组数。对于每组样例,第一行输入两个整数 n, m (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9),含义如题面所述。接下来的 n行,每行输入两个正整数 ai, bi (1 ≤ ai, bi ≤ 10^9),表示一个满减优惠。保证所有样例的 Σn ≤ 10^5。

输出格式

对每组用例,输出一个整数,表示鸡能购买的食物原价 x 最多为多少。

输入样例:

4
1 10
100 80
2 10
30 10
100 90
3 10
100 30
100 30
100 30
2 10
21 10
1000 1

输出样例:

10
110
100
10

题目分析

离散化和前缀和处理折扣即可。

不能二分答案再判断合法性, 因为能购买和不能购买并不能完整的划分为两个区间,它们是交错的。 还要注意数据范围,我认识有个朋友当时一直 WA ,第二天才看到数据范围才想起来会爆int。

代码实现

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#define x first 
#define y second 
using namespace std;
using LL = long long;
using PLL = pair <LL,LL>;

int t;
LL solve() {
    int n, m, a, b;
    cin >> n >> m;
    map <int,int> mp;
    for(int i = 0; i < n; ++i) {
        cin >> a >> b;
        mp[a] += b;
    }    
    int k = mp.size(), idx = 1;
    vector <PLL> ps(k + 1);
    LL prefix = 0;
    for(auto& t : mp) {
        ps[idx].x = t.x, ps[idx].y = t.y;
        ps[idx++].y = prefix += ps[idx].y;
    }
    for(int i = k; i >= 1; --i) if(ps[i].y + m >= ps[i].x) return ps[i].y + m; 
    return m;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) cout << solve() << '\n';
    return 0;
}
分类: PrefixSum

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status