这道题很简单,反思,学一下STL容器和哈希表
哈希表在C++中对应的容器是unordered_map
题目
给定 n 个石子,编号为 1~n。
其中第 i 个石子的价值为 ai。
你需要从中任意挑选若干个石子,并将挑选好的石子按照编号从小到大的顺序排成一排。
选中的石子在排好序后需要满足,对于任意两个相邻的石子(不妨设它们的编号为 x,y),x?y=ax?ay 均成立。
例如,当有 n=8 个石子,石子价值分别为 [3,4,4,6,6,7,8,9] 时,一些合理的选择方案如下:
选择 1,2,4 号石子,它们的价值分别为 3,4,6。1 号石子与 2 号石子相邻,2?1=4?3 成立。2 号石子与 4 号石子相邻,4?2=6?4 成立。所以方案合理。
选择 7 号石子。可以只选择一个石子,此时选取任何石子均为合理方案。
你的选择方案不仅需要合理,而且还要使得选中石子的价值总和尽可能大。
请计算并输出价值总和的最大可能值。
输入输出
第一行包含整数 n
第二行包含 n 个整数 a1,a2,…,an。
输出:一个整数,表示选中石子的价值总和的最大可能值。
思路
x?y=ax?ay,即 ax - x == ay - y
将ax - x 看作每个元素的树形,用哈希表h[ax - x] += ax
最后答案为哈希表中最大的元素
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int N = 200010;
int main()
{
unordered_map<int,LL> h;
unordered_map<int,LL>::iterator it;
int n;
cin >> n;
for (int i = 0; i < n; i ++ ){
int x;
cin >> x;
h[x - i] += x;
}
LL res = 0;
for(it = h.begin();it != h.end();it ++){
res = max(res,it->second);
}
cout << res;
return 0;
}