CodeForces 484B Maximum Value - c++编程基础

题意：

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 1000010 int 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; }