Slay the Dragon 二分 + 贪心

柔情只为你懂 2022-09-12 04:49 121阅读 0赞

二分+贪心找到最小花费，主要是边界有点麻烦

// Problem: C. Slay the Dragon
    // Contest: Codeforces - Educational Codeforces Round 114 (Rated for Div. 2)
    // URL: https://codeforces.com/contest/1574/problem/C
    // Memory Limit: 256 MB
    // Time Limit: 2000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<climits>
    #include<queue>
    #include<map>
    #include<set>
    #include<sstream>
    #include<cassert>
    #include<bitset>
    #include<list>
    #include<unordered_map>
    using namespace std;
    #define ff first
    #define ss second
    #define lowbit(x) (x&-x)
    #define pf(a) printf("%d\n",a)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define dbg(x) cout << #x << " = " << x << endl
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    #define fep(i,a,b) for(int i=b; i>=a; --i)
    typedef pair<int,int> PII;
    typedef long long ll;
    typedef unsigned long long ull;
    
    const int N=2e5+100;
    int n, m;
    ll a[N];
    vector<int> v[N];
    
    void solve()
    { 
    	scanf("%d", &n);
    	ll sum = 0;
    	a[0] = 1e18;
    	rep(i,1,n) 
    	{ 
    		scanf("%lld", &a[i]);
    		sum += a[i];
    	}	
    	sort(a+1, a+1+n);
    	
    	scanf("%d", &m);
    	while(m--)
    	{ 
    		ll defen, atta, ans = 0;
    		scanf("%lld %lld", &defen, &atta);
    		int t = lower_bound(a+1, a+1+n, defen) - a;
    		if(a[t] == defen)
    		{ 
    			if(sum-a[t]>=atta) ans = 0;
    			else ans = abs(a[t]+atta-sum);
    		}
    		else if(t > n) 
    		{ 
    			ans += defen - a[n];
    			if(sum - a[n] < atta) ans += (atta - sum + a[n]);
    		}
    		else
    		{ 
    			ll res = 0;
    			res += abs(a[t-1]-defen);
    			ll s1 = sum - a[t-1];
    			if(s1 < atta) res += atta - s1;
    			
    			ll xx = 0;
    			if(a[t] >= defen) { 
    				ll s3 = sum - a[t];
    				if(s3 < atta) xx += atta - s3;
    			}
    			
    			ll cnt = 0;
    			cnt += abs(a[t]-defen);
    			ll s2 = sum - a[t];
    			if(s2 < atta) cnt += atta - s2;
    			ans = min({ res, cnt,xx});
    			
    		}
    		printf("%lld\n", ans);
    		//cout << " t = " << t << " " << ans << endl;
    		//cout << t << endl;
    	}
    }
    
    int main()
    { 
    		solve();
    	return 0;
    }