这道世纪难题，谁能用c++写

Question

题目描述
现有
�
n位英雄，每位英雄有力量属性。需要击败防御力
�
x ，攻击力
�
y的巨龙，需要满足：

花费1金币，令某位英雄力量加一
选择一位英雄进攻，该英雄的力量至少为
�
x
其他英雄防守，其他英雄的力量之和至少为
�
y
现在有
�
m条恶龙，请你依次回答击败当前这条恶龙所需要花费的最少金币。

输入格式
第一行包含一个整数
�
(
2
≤
�
≤
2
∗
1
0
5
)
n(2≤n≤2∗10
5
)。 第二行包含
�
n个整数
�
1
,
�
2
,
.
.
.
,
�
�
(
1
≤
�
�
≤
1
0
12
)
a
1
​
,a
2
​
,...,a
n
​
(1≤a
i
​
≤10
12
)表示英雄的力量值。 第三行包含一个整数
�
(
1
≤
�
≤
2
∗
1
0
5
)
m(1≤m≤2∗10
5
)表示恶龙的数量。 以下
�
m行每行包含两个整数
�
,
�
(
1
≤
�
,
�
≤
1
0
18
)
x,y(1≤x,y≤10
18
)表示当前恶龙的防御力和攻击力。

输出格式
对于每个恶龙输出一个整数表示需要击败它所需要花费的最少金币。

样例
输入数据 1
4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7
输出数据 1
1
2
4
0
2
样例解释
为了击败第一条恶龙, 你可以将第三个勇者的力量增加1, 那么英雄们的力量值将会是
[
3
,
6
,
3
,
3
]
[3,6,3,3].为了击败这条恶龙，我们可以令第一个英雄出战。
谁能做出来这道世纪难题

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> heroes(n);
    for (int i = 0; i < n; i++) {
        cin >> heroes[i];
    }
    
    int m;
    cin >> m;
    
    for (int i = 0; i < m; i++) {
        long long x, y;
        cin >> x >> y;
        
        sort(heroes.begin(), heroes.end(), greater<int>());
        
        int cost = 0;
        int total_power = 0;
        for (int j = 1; j < n; j++) {
            total_power += heroes[j];
        }
        
        if (heroes[0] >= x) {
            cout << cost << endl;
        } else {
            int required_power = x - heroes[0];
            if (total_power >= y) {
                cout << cost + required_power << endl;
            } else {
                cout << cost + required_power + (y - total_power) << endl;
            }
        }
    }
    
    return 0;
}

通过读取输入并按照题目要求计算每个恶龙所需的最少金币，输出结果，代码中使用了 vector 容器来存储英雄的力量值，并进行相应的计算。你好好试试，我这里dev c++是正常跑的

Answer 2

错了啊

Answer 3

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> heroes(n);
    for (int i = 0; i < n; i++) {
        cin >> heroes[i];
    }
    
    int m;
    cin >> m;
    
    for (int i = 0; i < m; i++) {
        long long x, y;
        cin >> x >> y;
        
        sort(heroes.begin(), heroes.end(), greater<int>());
        
        int cost = 0;
        int total_power = 0;
        for (int j = 1; j < n; j++) {
            total_power += heroes[j];
        }
        
        if (heroes[0] >= x) {
            cout << cost << endl;
        } else {
            int required_power = x - heroes[0];
            if (total_power >= y) {
                cout << cost + required_power << endl;
            } else {
                cout << cost + required_power + (y - total_power) << endl;
            }
        }
    }
    
    return 0;
}

```c++

```

Answer 4

还是错的

Answer 5

我有一个思路是这样的，主要分几种情况讨论。首先记s=a[1]+a[2]+...+a[n]，即所有英雄力量之和。那么对于当前的恶龙

case1，如果我们选取进行攻击的英雄的a[i]<x，那么首先需要消耗c1=x-a[i]，同时其他英雄的的力量之和为s-a[i]，为了防御可能带来的消耗是c2，那么需要保证s-a[i]+c2>=y，即c2>=y-s+a[i]，但是注意c2其实是不需要取负数的，所以应该修正为c2>=max(y-s+a[i],0)。于是，我们还需要继续细分两种情况。

case1.1，如果y-s+a[i]>0，即s-y<a[i]<x，那么总消耗是c1+c2=x-a[i]+y-s+a[i]=x+y-s，是一个常数。即，如果我们选择那些满足s-y<a[i]<x的作为攻击的英雄，那么总消耗是x+y-s

case1.2，如果y-s+a[i]<=0，即a[i]<=s-y，那么总消耗是c1+c2=x-a[i]+0=x-a[i]。即，如果我们选那些满足a[i]<=s-y(因为都是整数，等价于a[i]<s-y-1)且a[i]<x的作为攻击的英雄，我们应该选择a[i]最大的，此时的消耗为x-a[i]

case2，如果我们选取攻击的英雄的a[i]>=x，那么首先要消耗c1=0(无消耗)，为了防御带来的可能消耗是c2>=max(y-s+a[i],0)。继续细分为两种情况

case2.1，如果y-s+a[i]>0，即a[i]>s-y(或者说a[i]>=s-y+1)，那么消耗为y-s+a[i]，即如果我们选择那些满足a[i]>=x且a[i]>=s-y+1的作为攻击英雄，那么应该选择a[i]最小的，此时消耗为y-s+a[i]
case2.2，如果y-s+a[i]<=0，即a[i]<=s-y，那么消耗为0，即如果我们选择那些满足x<=a[i]<=s-y的作为攻击英雄，那么总消耗为0。

总结一下，
情况1，如果我们选择那些满足s-y<a[i]<x的作为攻击的英雄，总消耗是x+y-s，和选择哪个a[i]无关。
情况2，如果我们选那些满足a[i]<s-y-1且a[i]<x的作为攻击的英雄，我们应该选择a[i]最大的，此时的消耗为x-a[i]
情况3，如果我们选择那些满足a[i]>=x且a[i]>=s-y+1的作为攻击英雄，那么应该选择a[i]最小的，此时消耗为y-s+a[i]
情况4，如果我们选择那些满足x<=a[i]<=s-y的作为攻击英雄，那么总消耗为0。

对于每一个恶龙，检查上面四种情况的答案，选择最小的即可。需要对a进行排序，然后每一种情况通过二分来计算答案，复杂度是O(mlogn)吧。

Answer 6

要注意的是，不是每种情况都是"有效"的("有效"指一定能找到一个答案)，对于"无效"情况跳过即可

Answer 7

代码
咋写

Answer 8

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7537803

Answer 9

题目名称叫什么？