CodeForces 484B Maximum Value-白红宇

CodeForces 484B Maximum Value

阅读量：5111 次

发布时间：2019-06-13

本文共 1292 字，大约阅读时间需要 4 分钟。

意甲冠军：

a序列n（2*10^5）数字问道a[i]>=a[j]如果是 a[i]%a[j]最大值是多少

思路：

感觉是一道挺乱来的题……

我们能够将ans表示为a[i]-k*a[j] 这样我们枚举k仅仅要知道比k*a[j]大可是不到(k+1)*a[j]的值就好了考虑到a[i]仅仅要10^6大因此能够用一个last数组记录小于等于i的数组中的数字因此仅仅要拿出last[(k+1)*a[j]-1]就好

暴力可能会T有一些能够让程序加速的方法输入开挂 a数字去重从大到小枚举a[i]当ans>=a[i]时候能够break

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;typedef long long LL;#define N 200010#define M 1000010int a[N], last[M];int n, ans;inline void scand(int &ret) { char c; ret = 0; while ((c = getchar()) < '0' || c > '9') ; while (c >= '0' && c <= '9') ret = ret * 10 + (c - '0'), c = getchar();}int main() { scand(n); for (int i = 1; i <= n; i++) { scand(a[i]); last[a[i]] = a[i]; } for (int i = 1; i < M; i++) { if (!last[i]) last[i] = last[i - 1]; } sort(a + 1, a + n + 1); n = unique(a + 1, a + n + 1) - a - 1; for (int i = n - 1; i >= 1; i--) { if (a[i] <= ans) break; for (int j = a[i] * 2; j < M && j - a[i] <= a[n]; j += a[i]) { ans = max(ans, last[j - 1] % a[i]); } ans = max(ans, last[M - 1] % a[i]); } printf("%d\n", ans); return 0;}

转载于:https://www.cnblogs.com/hrhguanli/p/4664051.html

你可能感兴趣的文章