FJNU第二十届低年级程序设计竞赛(正式赛)-1011 Problem-G-PY

问题 G: PY

时间限制: 1 Sec  内存限制:128 MB

题目描述

flag的两个队友每周都会到不同的地方做不可描述的PY交易，经过长时间的观察，flag发现他们所到的位置排成了一条直线，将他们标记成：1、2、3、4....n，发现他们每次去某个地方做不可描述的PY交易时都会留下一个奇怪的数字，在位置i会留下数字ai，flag坚信这是他两个PY队友交易的暗号，于是经过长期的研究flag发现了一个破解他们PY交易的函数F(i, j),函数可以表示成F(i, j) = ai + aj + | i - j |，只需要计算出最大的F(i, j)就能知道他们PY交易的秘密了。

输入

输入包含多组样例 第一行一个整数T表示数据组数（T <= 20） 对于每组数据第一行是一个正整数n表示位置的个数（2 <= n <= 1e5） 接下来一行n个数字ai表示每个位置的数字（1 <= ai <= 1e9）

输出

对于每组样例输出一个数字表示F(i, j)中的最大值

样例输入

3 5 1 2 3 4 5 5 5 4 3 2 1 5 1 2 5 3 4

样例输出

10 10 11

提示

第一组样例：选择第一个位置和第五个位置，那么结果 = 5 + 1 + |1 - 5| = 10 第二组样例：选择第一个位置和第五个位置，那么结果 = 1 + 5 + |1 - 5| = 10 第三组样例：选择第三个位置和第五个位置，那么结果 = 5 + 4 + |3 - 5| = 11

思路：要求 F(i, j) = ai + aj + | i - j |，可以想到分别从左向右扩张：即若 ak - ai > k - i  则k相对i为更优解 ，和从右向左扩张：即若 ak-aj > j - k 则k相对j为更优解.

设k1为从左到右的最优解，k2为从右到左的最优解，有k1<=k2.

证明：反证法

假若k1>k2,则  有a(k2) > a(k1)

 ak1 - ak2 < k1 - k2,

则从右到左不能从k1 扩张到 k2，矛盾.   

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <iostream> // C++头文件，C++完全兼容C #include <algorithm> // C++头文件，C++完全兼容C #define fre freopen("in.txt","r",stdin) //以文件代替控制台输入，比赛时很常用，能缩短输入测试样例的时间 #define INF 0x3f3f3f3f #define inf 1e60 using namespace std; // C++头文件，C++完全兼容C #define N 100005 // 宏定义 #define LL long long / /宏定义 int num[N]; int v1[N],v2[N]; //记录分别从左和右可以进行扩张的数的坐标 int main() { //fre; //以文件代替控制台输入，比赛时很常用，能缩短输入测试样例的时间 int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&num[i]); int s = 0; //左边从0开始往右扩张 int p = 1; int cot1 = 0; v1[cot1++]=s; while(p<n-1){ //不能把 第n个记进去 if(num[p]-num[s] > p-s){ v1[cot1++]=p; //满足扩张条件，则计入数组 s=p; } p++ } s = n-1; //右边从n-1开始从左扩张 p = n-2; int cot2 = 0; v2[cot2++]=s; while(p>0){ //不能把第0个记进去 if(num[p]-num[s] > s-p){ v2[cot2++]=p; //满足扩张条件则计入数组 s=p; } p--; } int ans; //两个数组的数最大项可能是同一个，除此之外不会冲突 分类讨论即可 if(v1[cot1-1]==v2[cot2-1]){ //若最大项为同一个 ans = max(num[v1[cot1-1]] + num[v1[cot1-2]] +v1[cot1-1] - v1[cot1-2] , num[v2[cot2-1]] + num[v2[cot2-2]]+ v2[cot2-2] - v2[cot2-1]); }else{ //若最大项不同 ans = num[v1[cot1-1]] + num[v2[cot2-1]] + v2[cot2-1] -v1[cot1-1]; } printf("%d\n",ans); } }