0分求调，样例过了

n_bluetea @ 2024-06-24 23:16:46

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

#define int long long
const int maxn = 1e6+10;

int n, m, s;
int w[maxn], v[maxn], l[maxn], r[maxn];
int pre_w[maxn], pre_v[maxn];

int check(int x){
    memset(pre_w,0,sizeof(pre_w));
    memset(pre_v,0,sizeof(pre_v));
    // 计算前缀和: 前n个矿石的重量和价值
    for(int i=1; i<=n; i++){
        pre_w[i] = pre_w[i-1] + (w[i]>=x ? w[i] : 0);
        pre_v[i] = pre_v[i-1] + (w[i]>=x ? v[i] : 0);
    }

    int res = 0;
    for(int i=1; i<=m; i++){
        res += (pre_w[r[i]] - pre_w[l[i]-1]) * (pre_v[r[i]] - pre_v[l[i]-1]);
    }

    if(res>=s) return 1;
    else       return 0;
}

void run(){
    cin >> n >> m >> s;

    int minn = 0x3f3f3f3f;
    int maxx = 0;
    for(int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
    }

    for(int i=1; i<=m; i++){
        cin >> l[i] >> r[i];
    }

    int left = 0, right = 1e18;

    while(left<right){
        int mid = left + (right-left)/2;
        if(check(mid)){
            left = mid+1;
        }
        else{
            right = mid;
        }
    }

    cout << abs(s-left+1) << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while(T--){
        run();
    }
    return 0;
}

by ABCgfed @ 2024-06-25 10:07:13

hack

6 1 20
2 6
3 5
5 4
8 3
7 2
4 1
2 5

答案

7

by ABCgfed @ 2024-06-25 10:08:34

已AC

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

#define int long long
const int maxn = 1e6+10;

int n, m, s;
int w[maxn], v[maxn], l[maxn], r[maxn];
int pre_w[maxn], pre_v[maxn];

int checkpoint=0;
long long minimum=99999999999999999; 

int check(int x){
    memset(pre_w,0,sizeof(pre_w));
    memset(pre_v,0,sizeof(pre_v));
    // 计算前缀和: 前n个矿石的重量和价值
    for(int i=1; i<=n; i++){
        pre_w[i] = pre_w[i-1] + (w[i]>=x ? 1/*不是w[i]*/ : 0);
        pre_v[i] = pre_v[i-1] + (w[i]>=x ? v[i] : 0);
    }

    int res = 0;
    for(int i=1; i<=m; i++){
        res += (pre_w[r[i]] - pre_w[l[i]-1]) * (pre_v[r[i]] - pre_v[l[i]-1]);
    }

    if(abs(res-s)<minimum){
        minimum=abs(res-s);
    } 
    if(checkpoint==1){
        cout<<min(abs(res-s),minimum)<<endl;
    }

    if(res>=s) return 1;
    else       return 0;
}

void run(){
    cin >> n >> m >> s;

    int minn = 0x3f3f3f3f;
    int maxx = 0;
    for(int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
    }

    for(int i=1; i<=m; i++){
        cin >> l[i] >> r[i];
    }

    int left = 0, right = 1e18;

    while(left<right){
        int mid = left + (right-left)/2;
        if(check(mid)){
            left = mid+1;
        }
        else{
            right = mid;
        }
    }

    checkpoint=1;
    checkpoint=check(left+1);
    //cout << abs(s-left+1) << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while(T--){
        run();
    }
    return 0;
}

by ABCgfed @ 2024-06-25 10:10:50

@n_bluetea 望关

by n_bluetea @ 2024-06-25 18:08:19

@ABCgfed 谢谢，已经关注

by n_bluetea @ 2024-06-25 22:39:09

@ABCgfed 我想问个问题，为什么要加这两行代码

checkpoint=check(left+1);

而不是直接cout<<minimum;

by ABCgfed @ 2024-06-26 13:18:25

@n_bluetea 可以的；因为我打二分习惯不更新最后一次判断结果而是将结果与先前的结果比较（众知二分有多种写法)，但为什么我总是忘了我是在改其他人的代码

by n_bluetea @ 2024-06-26 16:35:45

@ABCgfed 好的，谢谢