1010 求个最大值（数学）

1010: 求个最大值

时间限制: 1 Sec 内存限制: 128 MB
提交: 231 解决: 39
[提交][状态][讨论版]

题目描述

给出 n(1 <= n <= 200000)个数字 ai(1 <= ai <= 1000000)，i 为数字的下标，按输入顺序从 1 开始编号
一直到 n，求满足 ai >= aj 的最大的 ai % aj。

输入

第一行一个数字 n，第二行 n 个整数。

输出

题目要求的最大值。

样例输入

2
2 3

样例输出

提示

枚举aj 的倍数，用小于且最接近aj 的倍数的数来对aj 取余，

这里关于复杂度，是个级数求和，忘了怎么级数求和了，

用程序跑了下，算出来不会超...

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <map>
 9 #include <string>
10 #include <stack>
11 using namespace std;
12 typedef long long ll;
13 #define PI 3.1415926535897932
14 #define E 2.718281828459045
15 #define INF 0xffffffff//0x3f3f3f3f
16 #define mod 1000000007
17 const int MOD=1e9+7;
18  
19 const int M=1005;
20 int n,m;
21 int a[1000005],b[3000005];
22 int main()
23 {
24     int i,j,k,t;
25     int maxn,ans;
26     while(~scanf("%d",&n))
27     {
28         maxn=-1;
29         for(i=1; i<=n; i++)
30         {
31             scanf("%d",&a[i]);
32             maxn=max(a[i],maxn);
33         }
34         sort(a+1,a+n+1);
35         a[n+1]=2*maxn+1000000;
36         for(j=1; j<=n; j++)
37         {
38             for(i=a[j]+1; i<=a[j+1]; i++) //把n倍a[j]最接近的数打表
39                 b[i]=a[j];
40         }
41         ans=0;
42         for(j=1; j<=n; j++)
43             for(i=2*a[j]; i<=maxn+a[j]; i+=a[j])
44                 ans=max(ans,b[i]%a[j]);
45         printf("%d
",ans);
46     }
47     return 0;
48 }

还有一段代码，不懂，

 1 //#include <bits/stdc++.h>
 2 #pragma comment(linker, "/STACK:1024000000,1024000000")
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <iostream>
 7 #include <queue>
 8 #include <cmath>
 9 #include <string>
10 #include <map>
11 using namespace std;
12 #define INF 0x3f3f3f3f
13 using namespace std;
14 const int MAXN = 50007;
15 int a[MAXN],b[MAXN],c[MAXN];
16 int temp[MAXN<<2];
17  
18 int main()
19 {
20     int n;
21     while(scanf("%d",&n)!=EOF)
22     {
23         for(int i=0; i<n; ++i)
24             scanf("%d",&a[i]);
25         sort(a,a+n);
26         int ans=0,j=n-1;
27         for(int i=n-1; i>=0; --i)
28         {
29             int mx=-1;
30             while(j>=0&&(a[i]%a[j]>=mx))
31             {
32                 //cout<<a[i]<<" "<<a[j]<<" "<<a[i]%a[j]<<endl;
33                 mx=a[i]%a[j];
34                 j--;
35                 //cout<<a[i]<<" "<<a[j]<<" "<<a[i]%a[j]<<endl;
36             }
37          //   cout<<"o"<<endl;
38             j++;
39             // else break;
40             if(j>i)j=i;
41             ans=max(ans,mx);
42             if(j<0)break;
43         }
44         cout<<ans<<endl;
45     }
46     return 0;
47 }
48 /*
49 9
50 1 4 5 7 10 16 21 39 78
51 */

View Code