首页 > 代码库 > 一天一道算法题---5.26---思维锻炼

一天一道算法题---5.26---思维锻炼

2024-07-06 04:22:46   227人阅读

感谢 微信平台： 一天一道算法题 -----  大家没事都可以去关注他 --- 不是做广告的----

题目大意：  给你一个长度为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\n",result , l+1 , r+1 ); //分别+1 是因为求的是 元素位置
40     }    
41     return 0;
42 }
View Code

感觉　很忙　没时间　却还是　不停的ｌｏｌ　受不了。。。

大神 太流弊了 ！！！    我还是少考虑了一种情况 可能后面存在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\n", result, l + 1, r + 1); //分别+1 是因为求的是 元素位置
37         }
38         return 0;
39 }
View Code

 

 

 

 


联系
我们