P1314-聪明的质检员

古城微笑少年丶 2023-06-01 08:47 32阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     4 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     5 #define INF 0x3f3f3f3f3f3f3f3f
     6 #define pb push_back
     7 #define maxn 2005390
     8 typedef long long ll;
     9 
    10 inline ll read()
    11 {
    12     ll ans = 0;
    13     char ch = getchar(), last = ' ';
    14     while(!isdigit(ch)) last = ch, ch = getchar();
    15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    16     if(last == '-') ans = -ans;
    17     return ans;
    18 }
    19 inline void write(ll x)
    20 {
    21     if(x < 0) x = -x, putchar('-');
    22     if(x >= 10) write(x / 10);
    23     putchar(x % 10 + '0');
    24 }
    25 ll n,m,S;
    26 ll w[maxn],v[maxn];
    27 ll L[maxn],R[maxn];
    28 ll pren[maxn],preV[maxn];
    29 ll rnt = INF;
    30 //ll MIN = INF,MAX = 0;
    31 bool C(ll d)
    32 {
    33     ll ans = 0;
    34     _for(i,1,n+1)
    35         if(w[i]>=d)
    36             pren[i] = pren[i-1]+1,preV[i] = preV[i-1]+v[i];
    37         else
    38             pren[i] = pren[i-1],preV[i] = preV[i-1];
    39 
    40     _for(i,1,m+1)
    41         ans += (pren[R[i]]-pren[L[i]-1])*(preV[R[i]]-preV[L[i]-1]);
    42     rnt = min(rnt,llabs(ans-S));
    43     if(ans > S)
    44         return true;
    45     return false;
    46 }
    47 ll solve()
    48 {
    49     ll lb = 0,ub = INF;
    50     while(lb < ub)
    51     {
    52         ll mid =  lb+(ub-lb)/2;
    53         memset(pren,0,sizeof(pren));
    54         memset(preV,0,sizeof(preV));
    55         if(C(mid)) lb = mid+1;
    56         else ub = mid;
    57     }
    58     return rnt;
    59 }
    60 int main()
    61 {
    62  //    freopen("testdata.in","r+",stdin);
    63     n = read(),m = read(),S = read();
    64     _for(i,1,n+1)
    65     {
    66         w[i] = read();
    67         v[i] = read();
    68     //    MAX = max(MAX,w[i]);
    69     //    MIN = min(MIN,w[i]);
    70     }
    71     _for(i,1,m+1)
    72     {
    73         L[i] = read();
    74         R[i] = read();
    75     }
    76     write(solve());
    77     return 0;
    78 }

转载于:https://www.cnblogs.com/Asurudo/p/11614956.html