【HDU】6047 - Maximum Sequence（思维）

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int a[250000+5];
int maxx[250000+5];
vector<int> b;
const int MOD = 1e9 + 7;
int main()
{
    int n;
    int ans;
    while (~scanf ("%d",&n))
    {
        ans = 0;
        for (int i = 1 ; i <= n ; i++)
            scanf ("%d",&a[i]);
        b.clear();
        b.resize(n);
        for (int i = 0 ; i < n ; i++)
            scanf ("%d",&b[i]);
        maxx[n] = a[n]-n;
        for (int i = n-1 ; i >= 1 ; i--)
            maxx[i] = max(maxx[i+1],a[i]-i);
        sort(b.begin(),b.end());
        int t = -INF;       //后面数的最大值 
        for (int i = 0 ; i < n ; i++)
        {
            int num = max(maxx[b[i]],t);
            t = max(t,num-(n+i+1));
            ans = (ans + num) % MOD;
        }
        printf ("%d\n",ans);
    }
    return 0;
}