想了一天的题目QAQ 毛线数列的最值

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <string>
 7 #include <cstdlib>
 8 using namespace std;
 9 const int maxn=10+1e6;
10 #define  ll long long 
11 int n;
12 int b[maxn],c[maxn];
13 struct node
14 {
15     int date,biaoji;
16 }Node[maxn];
17 bool cmp(const node a,const node b)
18 {
19     if(a.date==b.date )
20     return a.biaoji <b.biaoji ;
21     return a.date <b.date ;
22 }
23 int main()
24 {    
25     int n;
26     while(cin>>n)
27     {   
28         memset(b,0,sizeof(b));
29         memset(c,0,sizeof(c));
30         ll ma=-1;
31         for(int i=1;i<=n;i++)
32         {
33             cin>>Node[i].date ;
34             Node[i].biaoji=i; 
35         }
36         sort(Node+1,Node+n+1,cmp);
37         b[n]=c[n]=Node[n].biaoji ;
38         for(int i=n-1;i>-1;i--)
39         {
40             if(Node[i].biaoji >b[i+1]) b[i]=Node[i].biaoji ;
41             else
42             b[i]=b[i+1];
43             if(Node[i].biaoji <c[i+1]) c[i]=Node[i].biaoji ;
44             else
45             c[i]=c[i+1];
46         }
47         
48         for(int i=1;i<=n-1;i++)
49         {
50             ll temp=max(abs(Node[i].biaoji -b[i+1]),abs(Node[i].biaoji -c[i+1]));
51             ma=max(ma,Node[i].date*temp);
52         }
53         cout<<ma<<endl;
54     }
55 }

毛线数列最值

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 195 Accepted Submission(s) : 11

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

halfyarn找你写个简单的题？好哒！给你n个整数,现在要求你选择两个位置的数，例如选择第pos_a个数a，和第pos_b个数b,给定ans=min(a,b)*abs(pos_a-pos_b),输出ans的最大值。

Input

第一行输入一个n代表有n个数，接下来的一行输入n个整数; 2<=n<=1e6; 1<=a,b<=1e6; 注意多组输入;

Output

ans的最大值;

Sample Input

4
1 2 2 2

Sample Output

4

首先这题题意很简单就是求max(min(a,b)*abs(pos_a-pos_b);
如果我们直接两个for循坏的话，时间复杂度是0（n^2）,会超时的，这里有一种时间复杂度是o(n)的方法；
我们先把这n个数据排序，从大到小，但是下标不变；比如
1 4 3 2
1 2 3 4

1 2 3 4
1 4 3 2
这样排好后，直接从i=1遍历到i=n-1;date[i]*(个数差),因为date已经从小到大排序了，所以只要考虑后面的大小，所以我们就要找第i个数据后的个数最大值和最小值就好，慢慢理解代码