感谢 微信平台： 一天一道算法题 ----- 大家没事都可以去关注他 --- 不是做广告的----
题目大意： 给你一个长度为n的整数序列A1，A2，……,An,找出两个整数Ai和Aj(i<j),使得Ai-Aj尽量大
反正 暴力肯定超时..... 数据大小 我也就给出了 反正 尽量用最好算法去解 就是了
嗯 它给的是o(n)的时间复杂度和空间度 但是很容易转换成o(1)空间度 o(n)时间复杂度的写法
这边给出个 与这题意相同的一个 题目 发现竟然是我以前WA的 怪不得 那么熟悉 。。。
哎 戳我
好吧 无限WA中 不管了 先把错误代码贴上来 郁闷……
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm>//这边 要是定义了这个头文件 直接用它里面的min max函数 对于下面求最值 更加方便 但运行速度没有先if判断快 而且if更加直观点 就是有点繁琐... 4 using namespace std; 5 6 int main() 7 { 8 int t , n; 9 long long temp , l , r; 10 long long x , y; 11 long long num; 12 long long mmin , mmax , result; 13 scanf( "%d",&t );//T组数据 14 while( t--) 15 { 16 scanf( "%d",&n );//n个元素大小的数组 17 scanf( "%lld %lld",&x,&y ); 18 mmax = x;//第一个元素 19 mmin = y;//第二个元素 20 l = temp = 0;//左边元素位置 temp起到 暂时存储的作用 如果没有小的元素出现 就不需要改变 L 的值 21 r = 1;//右边元素位置 22 result = x-y; 23 for( int i = 2 ; i<n ; i++ ) 24 { 25 scanf( "%lld",&num );//其余的n-2个元素 26 if( num<mmin ) 27 { 28 mmin = num; 29 result = mmax - mmin; 30 r = i; 31 l = temp; 32 } 33 if( num>mmax ) 34 { 35 mmax = num; 36 temp = i; 37 } 38 } 39 printf( "%lld %lld %lld ",result , l+1 , r+1 ); //分别+1 是因为求的是 元素位置 40 } 41 return 0; 42 }
感觉 很忙 没时间 却还是 不停的ｌｏｌ 受不了。。。
大神 太流弊了 ！！！ 我还是少考虑了一种情况 可能后面存在2个更大的元素 但是差值也同样更大
值得 记住
// 还好 晓爷 提醒我了 竟然 贴错代码了 昨夜 偏头痛
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 using namespace std; 5 6 int main() 7 { 8 int t, n; 9 long long temp, l, r; 10 long long x, y; 11 long long num; 12 long long mmax, result; 13 scanf("%d", &t);//T组数据 14 while (t--) 15 { 16 scanf("%d", &n);//n个元素大小的数组 17 scanf("%lld", &x); 18 mmax = x; 19 l = temp = 0;//左边元素位置 temp起到 暂时存储的作用 如果没有小的元素出现 就不需要改变 L 的值 20 r = 1;//右边元素位置 21 for (int i = 1; i<n; i++) 22 { 23 scanf("%lld", &num);//其余的n-1个元素 24 if (i == 1 || mmax - num > result) 25 { 26 result = mmax - num; 27 l = temp; 28 r = i; 29 } 30 if (num > mmax) 31 { 32 temp = i; 33 mmax = num; 34 } 35 } 36 printf("%lld %lld %lld ", result, l + 1, r + 1); //分别+1 是因为求的是 元素位置 37 } 38 return 0; 39 }