This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
$$
|A_0 - X| + |A_1 - X| + … + |A_{n-1} - X| \leq P
$$
を満たす整数$X$の個数を求める．これは凸関数になる．満たす区間の左端と右端を求めたいが，初期の区間を決めなければ二分探索でどっちにずらしていいか分からない．そのため，関数の極地を求めるためにまず三分探索する．極地が分かりその値を$v$とすると，左端を求めるのは$[-\infty, v]$と，右端を求めるのは$[v, \infty]$として二分探索すれば良い．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1LL<<30
#define EPS 1e-2
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
ll p ;
vector < int > v ;
bool f ( ll x ) {
ll sum = 0 ;
rep ( i , v . size ()) {
sum += abs ( v [ i ] - x );
}
return sum <= p ;
}
double g ( double x ) {
double sum = 0 ;
rep ( i , v . size ()) {
sum += abs ( v [ i ] - x );
}
return sum ;
}
class ModularInequality {
public :
int countSolutions ( vector < int > A , int P ) {
v = A ;
p = P ;
double l = - 4 * INF , r = 4 * INF ;
rep ( i , 2000 ) {
double a = ( l + l + r ) / 3.0 ;
double b = ( l + r + r ) / 3.0 ;
if ( g ( a ) > g ( b )) l = a ;
else r = b ;
}
if ( g ( l ) >= P + EPS ) return 0 ;
ll left = l , right = 4 * INF ;
while ( right - left > 1 ) {
ll mid = ( left + right ) / 2 ;
if ( f ( mid )) left = mid ;
else right = mid ;
}
ll a = left + 1 ;
left = - 4 * INF , right = l + 1 ;
while ( right - left > 1 ) {
ll mid = ( left + right ) / 2 ;
if ( f ( mid )) right = mid ;
else left = mid ;
}
ll b = left + 1 ;
return a - b ;
}
};