上海市计算机学会竞赛平台2022年10月月赛丙组组队竞赛

有𝑛n同学想要参加小爱组建的一支信息学竞赛队伍，每位同学有能力值𝑎𝑖ai​与热情度𝑏𝑖bi​。

小爱认为，如果队伍当中，能力值最大与能力值最小选手之间，能力差值大于给定𝑋X，会导致能力差距过大、不利于团队的学习与凝聚力。因此，请你帮助小爱计算下，如何选择队伍的选手，才能使所有选手的能力差值小于等于𝑋X，且热情度最大。

输入格式

输入第一行，一个正整数𝑛n，表示有𝑛n位选手
接下来𝑛n行，每行两个正整数𝑎𝑖,𝑏𝑖ai​,bi​表示每位选手的能力值与热情度。
最后一行，一个正整数𝑋X，表示小爱希望的能力差值上限

输出格式

输出一个整数，表示满足条件的情况下，最大热情度的值

数据范围

• 对于30%30%的数据，1≤𝑛≤1001≤n≤100
• 对于60%60%的数据，1≤𝑛≤1041≤n≤104
• 对于100%100%的数据，1≤𝑛≤105,1≤𝑥≤109,1≤𝑎𝑖,𝑏𝑖≤1091≤n≤105,1≤x≤109,1≤ai​,bi​≤109

样例数据

输入:

5
10 21
20 34
30 27
40 89
50 54
20

输出:

170

说明:

选第3、4、5个选手。
能力值分别为30、40、50，不超过50-30=20给定的能力差值上限20
此时热情度为27+89+54=170

详见代码:

#include <bits/stdc++.h>
using namespace std;
struct s 
{
    int a;
    long long b;
};
struct s st[100005];
bool cmp(struct s t1, struct s t2)
{
    return t1.a < t2.a;
} 
int main() 
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        scanf("%d %lld", &st[i].a, &st[i].b);
    }
    int x;
    cin >> x;
    sort(st + 1, st + n + 1, cmp);
    for (int i = 2; i <= n; i++) 
    {
        st[i].b += st[i - 1].b;
    }
    int pl = 1, pr = 1;
    long long maxb = 0;
    while (pr <= n) 
    {
        while (st[pr].a - st[pl].a <= x && pr <= n) 
        {
            pr++;
        }
        maxb=max(maxb, st[pr - 1].b - st[pl - 1].b);
        while (st[pl].a == st[pl + 1].a) 
        {
            pl++;
        }
        pl++;
    }
    cout << maxb << endl;
    return 0;
}

原文地址：https://blog.csdn.net/a121677_/article/details/140495518

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！