题目描述

暴力70分

样例

/*
暴力做法；
数组存放(ti, ci)，每次循环先sort(flag, ti降序，ci升序)，若存在，m -= ci, ti -= 1
这里的flag意思是若t1 <= k，flag = 0, 排序放到后面
若不存在，return 排序好后的arr[0].t1即T_total
时间复杂度为：m * sort
至此，csp系统里是70分，AcWing只过了3个数据；
*/

#include<iostream>
#include<algorithm>
#include<utility>

using namespace std;

int n, m, k;
const int N = 100010;
struct node{
    int t, c, flag;
}p[N];

bool cmp(node s1, node s2){//flag = 1, 若s的ti <= k, 则他的flag = 0
    if(s1.flag != s2.flag) return s1.flag > s2.flag;
    else if(s1.t != s2.t) return s1.t > s2.t;
    else return s1.c < s2.c;
}

int main(){
    cin >> n >> m >> k;

    for(int i = 0; i < n; i++){
        cin >> p[i].t >> p[i].c;
        p[i].flag = p[i].t > k ? 1 : 0;
    }

    while(m > 0){
        sort(p, p + n, cmp);
        if(p[0].flag == 0) break;//已经调整好
        else{
            if(m > p[0].c) m -= p[0].c;
            else break;
            p[0].t--;
            if(p[0].t == k) p[0].flag = 0;
        }
    }
    sort(p, p + n, cmp);
    cout << p[0].t;

    return 0;
}

二分100分

/*
暴力做法；
数组存放(ti, ci)，每次循环先sort(flag, ti降序，ci升序)，若存在，m -= ci, ti -= 1
这里的flag意思是若t1 <= k，flag = 0, 排序放到后面
若不存在，return 排序好后的arr[0].t1即T_total
时间复杂度为：m * sort
至此，csp系统里是70分，AcWing只过了3个数据；

因为m是10^9，所以肯定过不了，改进想法是如果对于每个(ti, ci)，都能快速求出ti减去的数量，时间复杂度就和m无关了
二分，全都缩小到x天, [k, p[0].t], 
check: sum((p[i].t - x) * p[i].c) <= m，这里注意需要用long long
这样结束，csp里100分
*/

#include<iostream>
#include<algorithm>

using namespace std;

int n, m, k;
const int N = 100010;
struct node{
    int t, c;
}p[N];

bool check(int u){
    long long res = 0;
    for(int i = 0; i < n; i++){
        if(p[i].t <= u) continue;
        res += (p[i].t - u) * p[i].c;
    }
    if(res <= m) return true;
    else return false;
}

int b_search(int max_t){
    int l = k, r = max_t;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main(){
    cin >> n >> m >> k;

    int max_t = 0;
    for(int i = 0; i < n; i++){
        cin >> p[i].t >> p[i].c;
        max_t = max(max_t, p[i].t);
    }
    cout << b_search(max_t);

    return 0;
}