Codeforces Round

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/48707217

题目链接： http://codeforces.com/contest/580

Ａ　求非递减区间的最大长度，递推即可

Ｂ　按ｍｏｎｅｙ值由大到小排序，求

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>  
#include <set>  
#include <map>  
#include <string.h>  
#include <queue>  
#include <sstream>  
#include <math.h>  
#include <stdlib.h>  
#include <functional>  
#include <vector>
#include <string.h>

using namespace std;

int n, m;
struct Node  
{
    long long val;
    long long fri;
}f[100010];

bool cmp(Node a, Node b)
{
    return a.val < b.val;
}

long long dp[100010];

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        memset(dp,0,sizeof(dp));
        for (int i = 1;i <= n;i++)
            scanf("%lld%lld", &f[i].val, &f[i].fri);

        sort(f + 1, f + 1 + n, cmp);

        long long ans = 0;
        long long tmp = 0;
        int pos = 1;
        for (int i = 1;i <= n;i++)
        {
            if (i != 1) tmp -= f[i - 1].fri;
            while (pos <= n && f[pos].val - f[i].val < m)
            {
                tmp += f[pos++].fri;
            }
            ans = max(ans, tmp);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Ｃ　由根节点进行ＤＦＳ遍历，遍历过程记录答案。