把所有人的位置和钥匙的位置排序，可以发现，最优的选择钥匙的方法一定是选择一段连续的区间，暴力枚举即可。当然，二分最优时间贪心去判断也是可以的，复杂度相对枚举更优。
#include<iostream> #include<cstdio> #include<queue> #include<cmath> #include<algorithm> #define ll long long using namespace std; int n, k; ll p; ll a[5005], b[10005]; bool check ( int mid ) { int i = 1, j = 1; while ( j <= k ) { if ( (ll)abs ( b[j] - a[i] ) + abs ( p - b[j] ) <= mid ) i ++; if ( i == n + 1 ) break; j ++; } return i == n + 1; } ll erfen ( ) { ll l = 0, r = 1e9, ans; while ( l <= r ) { int mid = ( l + r ) >> 1; if ( check ( mid ) ) { ans = mid; r = mid - 1; } else l = mid + 1; } return ans; } int main ( ) { //freopen ( "keys.in", "r", stdin ); //freopen ( "keys.out", "w", stdout ); scanf ( "%d%d%I64d", &n, &k, &p ); for ( int i = 1; i <= n; i ++ ) scanf ( "%I64d", &a[i] ); for ( int i = 1; i <= k; i ++ ) scanf ( "%I64d", &b[i] ); sort ( a + 1, a + 1 + n ); sort ( b + 1, b + 1 + k ); ll ans = erfen ( ); printf ( "%I64d", ans ); return 0; }
每次我们只需要找到下一个最小值，计算这段区间还剩下的牌的张数，再删除这个最小值即可。一道小模拟，考虑用数据结构维护。
原序列建成一棵线段树，结构体中维护区间和，区间最小值，以及最小值所在位置。区间和是牌张数的和，每次删除一个点，把这个点的最小值改成正无穷，就可以更新了。
查询时需要查询$1-pos$和$pos-n$两段区间，$pos$指现在上一次删除的点位置，判断两个区间最小值大小，优先删除后面的区间。
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; int n; int las[100005]; struct tree { ll sum; int mi, pos; } TR[100005*4]; struct node { int v, id; } a[100005]; bool cmp ( node a, node b ) { if ( a.v == b.v ) return a.id < b.id; return a.v < b.v; } void update ( int nd ) { TR[nd].sum = TR[nd << 1].sum + TR[nd << 1 | 1].sum; if ( TR[nd << 1 | 1].mi < TR[nd << 1].mi ) { TR[nd].mi = TR[nd << 1 | 1].mi; TR[nd].pos = TR[nd << 1 | 1].pos; } else if ( TR[nd << 1].mi < TR[nd << 1].mi ){ TR[nd].mi = TR[nd << 1].mi; TR[nd].pos = TR[nd << 1].pos; } else { TR[nd].mi = TR[nd << 1].mi; TR[nd].pos = min ( TR[nd << 1].pos, TR[nd << 1 | 1].pos ); } } void build ( int nd, int l, int r ) { if ( l == r ) { TR[nd].sum = 1; TR[nd].mi = a[l].v; TR[nd].pos = a[l].id; return ; } int mid = ( l + r ) >> 1; build ( nd << 1, l, mid ); build ( nd << 1 | 1, mid + 1, r ); update ( nd ); } void add ( int nd, int l, int r, int pos, int d ) { if ( l == r ) { TR[nd].sum += d; if ( !TR[nd].sum ) TR[nd].mi = 0x3f3f3f3f; return ; } int mid = ( l + r ) >> 1; if ( pos <= mid ) add ( nd << 1, l, mid, pos, d ); else add ( nd << 1 | 1, mid + 1, r, pos, d ); update ( nd ); } tree query ( int nd, int l, int r, int L, int R ) { if ( l >= L && r <= R ) return TR[nd]; tree ans; ans.mi = 0x3f3f3f3f; ans.sum = 0; ans.pos = 0; int mid = ( l + r ) >> 1; if ( L <= mid ) { tree tmp = query ( nd << 1, l, mid, L, R ); ans.sum += tmp.sum; if ( ans.mi > tmp.mi ) { ans.mi = tmp.mi; ans.pos = tmp.pos; } else if ( ans.mi == tmp.mi ) { ans.pos = min ( ans.pos, tmp.pos ); } } if ( R > mid ) { tree tmp = query ( nd << 1 | 1, mid + 1, r, L, R ); ans.sum += tmp.sum; if ( ans.mi > tmp.mi ) { ans.mi = tmp.mi; ans.pos = tmp.pos; } else if ( ans.mi == tmp.mi ) { ans.pos = min ( ans.pos, tmp.pos ); } } return ans; } int main ( ) { freopen ( "cards.in", "r", stdin ); freopen ( "cards.out", "w", stdout ); scanf ( "%d", &n ); for ( int i = 1; i <= n; i ++ ) { scanf ( "%d", &a[i].v ), a[i].id = i; } build ( 1, 1, n ); sort ( a + 1, a + 1 + n, cmp ); int pre = 1; ll ans = 0; for ( int i = 1; i <= n; i ++ ) { tree q1 = query ( 1, 1, n, pre, n ); tree q2 = query ( 1, 1, n, 1, pre ); int pos; if ( q1.mi <= q2.mi ) { pos = q1.pos; ans += query ( 1, 1, n, pre, pos ).sum; } else { pos = q2.pos; ans += q1.sum; ans += query ( 1, 1, n, 1, pos ).sum; } add ( 1, 1, n, pos, -1 ); pre = pos; } printf ( "%I64d", ans ); return 0; }
转换题意，我们要求的实际上是使$sum {left lceil frac{a_i}{d} ight ceil*d-a_i}<=k$成立的最大$d$，可以发现，对于同一个$a_i$来说，$left lceil frac{a_i}{d} ight ceil$的取值有$sqrt{a_i}$个，$n$个$a_i$就有$nsqrt{a_i}$个，我们可以把所有使$left lceil frac{a_i}{d} ight ceil$相同的$d$分成一组，处理下来，每一组$d$中的$left lceil frac{a_i}{d} ight ceil$都相同，此时这组$d$算出来的答案就具有二分性了。
接下来是如何分组的问题。我们设$x=left lceil frac{a_i}{d} ight ceil$，那么$x-1<frac{a_i}{d}<=x$，所以$frac{a_i}{x}<=d$，意味着，对于每一段连续相同的$x$，$d$的范围是可以确定的，因为是$>=$，我们就可以倒着处理$d$，每次算出一个范围的起点$d$，那么$leftlceilfrac{a}{d-1} ight ceil$就是下一段的$x'$，$left lceil frac{a}{x'} ight ceil$就是下一个范围的起点$d'$了。我们把每个起点存到结构体，排序加二分就行了。注意离散化。
可是$stl$好慢aaa！！怎么搞都t！！
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #define ll long long using namespace std; int n; vector < ll > vc; ll k, a[105]; void split ( ll a, vector < ll > &vc ) { for ( ll d = a; d; ) { ll x = ( a + d - 1 ) / d; ll k = ( a + x - 1 ) / x; vc.push_back ( k ); d = k - 1; } } bool check ( ll mid ) { ll ans = 0; for ( int i = 1; i <= n; i ++ ) { ans += ( a[i] + mid - 1 ) / mid * mid - a[i]; } return ans <= k; } int main ( ) { freopen ( "bamboo.in", "r", stdin ); freopen ( "bamboo.out", "w", stdout ); scanf ( "%d%I64d", &n, &k ); for ( int i = 1; i <= n; i ++ ) { scanf ( "%I64d", &a[i] ); split ( a[i], vc ); } sort ( vc.begin ( ), vc.end ( ) ); vc.erase ( unique ( vc.begin ( ), vc.end ( ) ), vc.end ( ) ); vc.push_back ( 10000000000000ll ); ll ans = 1; for ( int i = 0; i + 1 < vc.size ( ); i ++ ) { ll l = vc[i]; ll r = vc[i+1] - 1; ll sum = 0; if ( !check ( l ) ) continue; while ( l <= r ) { int mid = ( l + r ) >> 1; if ( check ( mid ) ) { sum = mid; l = mid + 1; } else r = mid - 1; } ans = max ( ans, sum ); } printf ( "%I64d", ans ); return 0; }