牛客oj---求最值(暴力+骗样例)

本文主要是介绍牛客oj---求最值(暴力+骗样例)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求最值

时间限制：
C/C++ 1秒，其他语言2秒
空间限制：
C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
给你一个长为n的序列a
定义f(i,j)=(i-j)2+g(i,j)2
g是这样的一个函数

求最小的f(i,j)的值，i!=j

输入描述:
第一行一个数n
之后一行n个数表示序列a
输出描述:
输出一行一个数表示答案
示例1
输入
4
1 0 0 -1
输出
1
备注:
对于100%的数据，2 <= n <= 100000 , |ai| <= 10000

**思路：**看的别人的代码，学会了怎么骗样例，，
如果内层循环没有j<=i+2000就超时了，这里堵了一把，假设在2000个之内就能找到答案；
ac code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int a[100005];
ll sum[100005];int main(){int n;cin>>n;sum[0]=0;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];}ll ans=99999999999999;for(int i=1;i<=n;i++){for(int j=i+1;j<=n&&j<=i+2000;j++){if(i!=j){ll t=(sum[j]-sum[i])*(sum[j]-sum[i])+(j-i)*(j-i);ans=min(ans,t);}}}cout<<ans<<endl;return 0;
}

这篇关于牛客oj---求最值(暴力+骗样例)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---