CF1574C Slay the Dragon

题意简述

给定一个数组，有若干次询问。对于每次询问，输入 $x$$x$ 和 $y$$y$，要求在原数组中对若干个数进行 $+1$$+1$，每次操作花费一枚金币。找到一个元素 $a$$a$，使得 $a>=x$$a>=x$ 且 除去 $a$$a$ 外数组的总和大于等于 $y$$y$。求最少金币数。

先说几句

一道有点难的贪心、二分、排序。建议难度 普及。

解题思路

输入数组后，进行排序。 对于每一个 $x$$x$ 和 $y$$y$，在数组中二分查找 lower_bound $x$$x$。

记 $k$$k$ 为 lower_bound(a, a+n, x)-a。

Part 1: $k=0$$k=0$

令 $s$$s$ 为除去 a[k] 的总和。如果 $s<y$$s<y$，则所需金币数为 $y-s$$y-s$。否则不要花费金币。

Part 2: $k<n$$k<n$

需要分情况考虑。

情况1

假设取英雄 $k$$k$ 打败龙。按照 Part 1 的方法计算金币数。

情况2

假设取英雄 $k-1$$k-1$ 打败龙。按照 Part 1 的方法计算金币数。

只要输出上面两种情况的较小值就可以了。

Part 3: 没有可选的英雄打败龙（$k=n$$k=n$）

按照贪心思想，我们要选攻击力最大的英雄来打龙。

先计算出 $s$$s$。如果 $s<y$$s<y$，则保护城堡的金币数是 $y-s$$y-s$，打败龙的金币数是 $x-a[maxi]$$x-a[maxi]$，总共金币数就是 y-s+x-a[maxi]。

否则，只需要花费英雄的金币，就是 x-a[maxi]。

Part 4: 优化

必须按照下面的内容优化，否则会超时！

1.使用 inline 内联函数。

使用 inline 内联函数可以提高函数调用效率。

2.预处理 $maxi$$maxi$ 和数组总和。

预处理过后，就不必反复循环计算了。

3.输入输出优化。

就是这三条语句：

xxxxxxxxxx
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);

奉上代码

千万不要抄，小心棕名！

xxxxxxxxxx
// 1574C Slay the Dragon
#include <bits/stdc++.h>
#define var long long
using namespace std;

var totalsum;
inline var getsumWithout(var a[], var n, var k)
{
    return totalsum-a[k];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    var n; cin>>n;
    var a[n];
    var maxi=0;
    for(var i=0; i<n; i++)
        cin>>a[i], totalsum+=a[i];
    sort(a, a+n);
    maxi=n-1;
        
    var T; cin>>T;
    while(T--)
    {
        var x, y; cin>>x>>y;
        var k=lower_bound(a, a+n, x)—a;
        if(k==0) 
        {
            var s=getsumWithout(a, n, k);
            if(s<y)
                cout<<y-s<<endl;
            else
                cout<<0<<endl;
            continue;
        }
        if(k!=n)
        {
            var res1;
            {
                var s=getsumWithout(a, n, k);
                if(s<y)
                    res1=y-s;
                else
                    res1=0;
            }
            var res2=x-a[k-1];
            {
                var s=getsumWithout(a, n, k-1);
                if(s<y)
                    res2+=y-s;
            }
            cout<<min(res1, res2)<<endl;
        }
        else
        {
            var s=getsumWithout(a, n, maxi);
            if(s<y)
                cout<<y-s+x-a[maxi]<<endl;
            else
                cout<<x-a[maxi]<<endl;
        }
    }

    return 0;
}