HDU-2017 多校训练赛2-1003-Maximum Sequence

ACM模版

描述

题解

这个题实际上就是一个尺取法，贪心控制左区间端点，右区间端点每次加一，右区间移动需要添加数据，左区间端点移动需要删除数据，就这样，我采用了多重集合搞，但是一开始一直 $CE$，后来发现我这里提交代码十次九次都要 $CE$，大概是丢包了吧，然后终于提交上了却 $WA$ 了，找了好久发现，原来是因为我删除操作，不能直接删除某一个数 $x$，因为这样会将所有的 $x$ 都删除，这显然是不行，我们希望只删除一个，所以换一种方式删除，先找到一个 x <script type="math/tex" id="MathJax-Element-135">x</script> 的位置，然后针对性的删除即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

const int MAXN = 2e5 + 5e4 + 10;
const int MOD = 1e9 + 7;

int n;
int a[MAXN << 1];
int b[MAXN];
multiset<int> si;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main(int argc, const char * argv[])
{
    while (cin >> n)
    {
        si.clear();
        for (int i = 1; i <= n; i++)
        {
            scan_d(a[i]);
            a[i] -= i;
            si.insert(a[i]);
        }
        for (int i = 1; i <= n; i++)
        {
            scan_d(b[i]);
        }
        sort(b + 1, b + n + 1);

        long long sum = 0;
        for (int i = 1, j = 1; i <= n; i++)
        {
            for (; j < b[i]; j++)
            {
                auto it = si.find(a[j]);
                si.erase(it);
            }
            auto it = si.end();
            it--;
            sum += *it;
            sum %= MOD;
            a[i + n] = *it - i - n;
            si.insert(a[i + n]);
        }

        cout << sum << 'n';
    }

    return 0;
}

最后

以上就是温婉樱桃为你收集整理的HDU-2017 多校训练赛2-1003-Maximum Sequence的全部内容，希望文章能够帮你解决HDU-2017 多校训练赛2-1003-Maximum Sequence所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。