HDU 6047 Maximum Sequence 思維

　　題目連結： http://acm.hdu.edu.cn/showproblem.php?pid=6047

　　題目描述： 有數組a, b長度都為n ......解釋起來好麻煩， 自己看題吧

　　解題思路： 由性質可知添加的n個數一定是單調遞減的， 是以我們可知最後的n個數一定是取了前 n+1的數中的某些數， 如果一個數大于下标其下标大的， 則更新

　　代碼： (徐文棟的， 很巧

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 250500;
const LL mod = (LL)1e9+7;
int n;
LL a[maxn], b[maxn];

signed main() {
    // freopen("in", "r", stdin);
    while(~scanf("%d", &n)) {
        a[n+1] = 0;
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);
        for(int i = n; i >= 1; i--) {
            a[i] -= i;
            a[i] = max(a[i], a[i+1]);
        }
        sort(b+1, b+n+1);
        LL ret = 0, flag = 0;
        for(int i = 1; i <= n; i++) {
            LL x = max(flag, a[b[i]]);
            ret = (ret + x) % mod;
            flag = max(flag, x-(n+i));
        }
        printf("%lld\n", ret);
    }
    return 0;
}      

View Code

　　思考： 這是我寫的最差的一篇部落格了......雖然其他的也不好， 這題我能夠想出來但是還是實作不出來.....瑪麗啊！

轉載于:https://www.cnblogs.com/FriskyPuppy/p/7248290.html