Codeforces 1320A Journey Planning【思维转换】

题目链接

题目大意：

  给出一串数，要求选择其中的一些数满足：(i-j=b_i-b_j)，其中 (i,j)为该数在原数组中的下标，(b_i,b_j) 为数值。

分析：

((i-j=b_i-b_j) Rightarrow (i-b_i=j-b_j))，因此可以求出每个数的数值和其下标的差值，然后按差值排序，差值相同的必然在一组，累加起来，求出最大即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
typedef long long ll;
const int N=2e5+5;
int b[N];
P city[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        city[i].second=i;
        city[i].first=b[i]-i;
    }
    sort(city+1,city+1+n);
    ll ans=0,res=0;
    for(int i=1;i<=n;i++)
    {
        if(i>1&&city[i].first==city[i-1].first)
            res+=b[city[i].second];
        else
        {
            ans=max(res,ans);
            res=b[city[i].second];
        }
    }
    ans=max(res,ans);
    printf("%lld
",ans);
    return 0;
}