当前位置: 首页 > news >正文

51nod 1421 最大MOD值

分析:首先去重排序,然后枚举a[i]的倍数,找到最大的a[j],使得a[j]小于a[i]的倍数,用二分法找,然后更新一下最大值。枚举a[i]和倍数复杂度为O(nlogn),二分O(logn),总的为O(n(logn)^2)。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=200005;
 6 int a[maxn],n;
 7 bool have[5*maxn];
 8 inline int Dich(int t,int l){
 9     if(a[n-1]<=t)return a[n-1];
10     if(a[l]>t)return a[l-1];
11     int r=n-1,m=(r+l)/2;
12     while(l<r&&l!=m){
13         if(a[m]==t)return a[m];
14         if(a[m]>t)r=m;
15         else l=m;
16         m=(l+r)/2;
17     }
18     return a[m];
19 }
20 int main(){
21     cin>>n;
22     int v;
23     memset(have,0,sizeof(have));
24     for(int i=0;i<n;i++){
25         cin>>v;
26         if(have[v]){
27             n--;i--;
28             continue;
29         }
30         a[i]=v;
31         have[v]=true;
32     }
33     sort(a,a+n);
34     int ans=0;
35     for(int i=0;i<n;i++){
36         int t=a[i]*2;
37         do{
38             int k=Dich(t-1,i+1)%a[i];
39             if(k>ans)ans=k;
40         }while((t+=a[i])<=a[n-1]);
41     }
42     cout<<ans<<endl;
43     return 0;
44 }

 

转载于:https://www.cnblogs.com/7391-KID/p/7071784.html

相关文章:

  • R语言-排序
  • idea 15安装步骤2017.6.25
  • 机器学习:绪论
  • JS(一)
  • spring data jpa mysql 悲观锁
  • 迅为IMX6开发板支持全网通4G模块丨GPS模块丨WIFI蓝牙丨千兆以太网
  • hackerrank Diameter Minimization
  • 如何开发一个Servlet
  • HDU1023 Train Problem II
  • Linux 定时任务的学习
  • 什么是编程语言
  • JavaSE--【转】网络安全之证书、密钥、密钥库等名词解释
  • Python基础 :正则表达式
  • 是否有网络
  • 是时候学一波STL了。。。
  • egg(89)--egg之redis的发布和订阅
  • java B2B2C 源码多租户电子商城系统-Kafka基本使用介绍
  • Java 最常见的 200+ 面试题:面试必备
  • JavaScript HTML DOM
  • Linux快速配置 VIM 实现语法高亮 补全 缩进等功能
  • React中的“虫洞”——Context
  • 不发不行!Netty集成文字图片聊天室外加TCP/IP软硬件通信
  • 解决iview多表头动态更改列元素发生的错误
  • 聚簇索引和非聚簇索引
  • 让你成为前端,后端或全栈开发程序员的进阶指南,一门学到老的技术
  • 让你的分享飞起来——极光推出社会化分享组件
  • 容器服务kubernetes弹性伸缩高级用法
  • 如何邀请好友注册您的网站(模拟百度网盘)
  • 设计模式走一遍---观察者模式
  • 正则与JS中的正则
  • ​二进制运算符:(与运算)、|(或运算)、~(取反运算)、^(异或运算)、位移运算符​
  • # Swust 12th acm 邀请赛# [ E ] 01 String [题解]
  • (07)Hive——窗口函数详解
  • (AtCoder Beginner Contest 340) -- F - S = 1 -- 题解
  • (C语言)编写程序将一个4×4的数组进行顺时针旋转90度后输出。
  • (html转换)StringEscapeUtils类的转义与反转义方法
  • (Java岗)秋招打卡!一本学历拿下美团、阿里、快手、米哈游offer
  • (MATLAB)第五章-矩阵运算
  • (二开)Flink 修改源码拓展 SQL 语法
  • (翻译)Quartz官方教程——第一课:Quartz入门
  • (六)软件测试分工
  • (原)本想说脏话,奈何已放下
  • (轉貼) 2008 Altera 亞洲創新大賽 台灣學生成果傲視全球 [照片花絮] (SOC) (News)
  • .Family_物联网
  • .net 4.0发布后不能正常显示图片问题
  • .NET CLR基本术语
  • .NET 的程序集加载上下文
  • [1]-基于图搜索的路径规划基础
  • [8481302]博弈论 斯坦福game theory stanford week 1
  • [ai笔记9] openAI Sora技术文档引用文献汇总
  • [Apio2012]dispatching 左偏树
  • [C++ 从入门到精通] 12.重载运算符、赋值运算符重载、析构函数
  • [CF226E]Noble Knight's Path
  • [JavaWeb学习] idea新建web项目
  • [Java基础]—JDBC