cf#276-B-Maximum Value-(数学+暴力)/(二分)

http://codeforces.com/contest/484/problem/B
n個の数をあげて、
n個の数の中でai%(aj)の最大値を求めて、ai>=ajを要求します
最初はいい考えはなかった
ajを列挙して、毎回探しに行きます k*ajの存在に最も近い数(k>=2)
どのように探すならば2つの方法があります1つは直接配列aを並べ替えて、毎回2分で最もk*ajに近い数を探します
複雑度はnlgnlgnであるべきである
vis配列を前に処理すると
vis[a[i] ]=a[i]
vis[i]=vis[i-1]
ではvis配列には,vis[i]がiに最も近い数(自分が存在すれば当然自分である)を格納する.
そこでajを列挙する場合は、vis【2*aj-1】、vis【3*aj-1】…vis【k*aj-1】にアクセスするだけです
複雑度はnlogn
列挙ajの複雑さはスクリーンと少し似ている. n/1+n/2+n/3+......n/nはnlogn程度
【もう1つ、列挙するときは、明らかに最大の数から列挙すべきで、答えができるだけ大きくなるので、枝を切ることができます.2つの方法は、大きいものから小さいものまで70+msです】
【枝をもう1本減らすことができます 】
2点以外の方法:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;

const double pi=acos(-1.0);
double eps=0.000001; 
__int64 min(__int64 a,__int64 b)
{return a<b?a:b;} 
__int64 max(__int64 a,__int64 b)
{return a>b?a:b;}

__int64 tm[3000123]; 
__int64 vis[3000123]; 
int main()
{
	__int64 i,j; 
	__int64 n;
	scanf("%I64d",&n);
		__int64 top=0;
	for (i=1;i<=n;i++)
	{
		scanf("%I64d",&tm[i]);  
		if (tm[i]>top) top=tm[i];
 		vis[tm[i]]=tm[i];
	}
 
	for (i=1;i<=top*2;i++)
		if (vis[i]==i)continue;
		else
			vis[i]=vis[i-1];

	int maxx=0;

	for (i=top;i>=1;i--)
	{ 
		if (vis[i]==i)
		{
			if (maxx>i-1) continue;
			for (j=2*i-1;j<=top*2;j+=i)
			{
				maxx=max(maxx,vis[j]%i);
			}
		}
	}
	printf("%d
",maxx);
	
	
	
	
	
	
	return 0;
	
}

二分のやり方
 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;

const double pi=acos(-1.0);
double eps=0.000001; 
__int64 min(__int64 a,__int64 b)
{return a<b?a:b;} 
__int64 max(__int64 a,__int64 b)
{return a>b?a:b;}

__int64 tm[3000123]; 
__int64 vis[3000123]; 
int main()
{
	__int64 i,j; 
	__int64 n;
	scanf("%I64d",&n);
		__int64 top=0;
	for (i=1;i<=n;i++)
	{
		scanf("%I64d",&tm[i]);  
		if (tm[i]>top) top=tm[i];
 		vis[tm[i]]=tm[i];
	}
	sort(tm+1,tm+1+n);
	n=unique(tm+1,tm+1+n)-tm-1; 
 
	int maxx=0;

	for (i=n;i>=1;i--)
	{ 
		int x=tm[i]; 
		int k=2;
		while(x*k-1<=top*2)
		{
			int it=upper_bound(tm+1,tm+1+n,x*k-1)-tm;
			it--; 
			if (tm[it]%x>maxx ) maxx=tm[it]%x; 
		if (maxx>=x-1) break;
			k++;
		}   
	}
	printf("%d
",maxx);
	
	
	
	
	
	
	return 0;
	
}