CodeForces 484B Maximum Value

题意:

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()) '9') ; while (c >= '0' && c = 1; i--) { if (a[i]

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:prev_permutation 函数
下一篇:C++实现DNS域名解析
相关文章

Codeforces Round #124 (Div. 2)

Codeforces Round #131 (Div. 2)

CodeForces 180E Cubes--后续指针--

Codeforces Round #133 (Div. 2)

CodeForces Round #125 (198C) -

CodeForces Round #116 (180E) - Cubes

CodeForces Round #118 (185A) - Plant

CodeForces Round #118 - Mushroo

CodeForces Round #119 (187A)

CodeForces Round #119 (187B) -

图文推荐

CodeForces 484B Maximum Value
ZOJ 3640 Help Me
CodeForces 484B Maximum Value
CF 518C(Anya and
CodeForces 484B Maximum Value
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-01 人气:1
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.071 (s). 10 q(s)