Ural 1010 Discrete Function
时间：2011-03-15 来源：watana
http://acm.timus.ru/problem.aspx?space=1&num=1010
方法一：单纯的枚举
枚举每两点对，判断是否两点间的点都此两点的连线下方，计算斜率，找出最佳点对
时间复杂度：O(N2)
方法二：改进后的枚举
对方法一进行改进，是否可以从某种角度，找出突破点，减少枚举量呢？
从数学角度入手，发现只有两点相邻，斜率能取得最大值，这样，只枚举相邻点即可
时间复杂度：O(N)
数据依然变态，听说全是longint的数据...我就用double过了...#include<stdio.h>
#include<math.h>
int main()
{
int i,n,index;
double x0,x1,k;
while(scanf("%d",&n)!=EOF)
{
scanf("%lf",&x0);
k=-99999999;
index=2;
for(i=2;i<=n;i++)
{
scanf("%lf",&x1);
if(fabs(x1-x0)>k)
{
k=fabs(x1-x0);
index=i;
}
x0=x1;
}
printf("%d %d\n",index-1,index);
}
return 0;
}
相关阅读 更多 +
排行榜 更多 +
