对于和规律或者数学有关的题真的束手无策啊QAQ
首先发现两个性质：
1、不管中间怎么碰撞，所有蚂蚁的相对位置不会改变，即后面的蚂蚁不会超过前面的蚂蚁或者落后更后面的蚂蚁。
2、因为所有蚂蚁速度一样，不管标号的话两只蚂蚁的碰撞相当于直接互相穿过，所以最初有多少蚂蚁方向向左，最后就有多少蚂蚁从左落下，向右同理。
总结一下又可以发现，比如有$cntl$只蚂蚁最初向左，$cntr$只蚂蚁最初向右，那么最后就是原位置的左边连续$cntl$只从左落下，原位置右边连续$cntr$只从右落下。我们将所有方向向左和向右的蚂蚁落下的时间分别排序，和原序列上一一对应即可。
#include<iostream> #include<cstdio> #include<algorithm> #define LL long long using namespace std; int n, b[100005], cntl, cntr; LL a[100005], L; double ans[100005], l[100005], r[100005]; int main ( ) { freopen ( "ant.in", "r", stdin ); freopen ( "ant.out", "w", stdout ); scanf ( "%I64d%d", &L, &n ); for ( int i = 1; i <= n; i ++ ) scanf ( "%I64d", &a[i] ); for ( int i = 1; i <= n; i ++ ) scanf ( "%d", &b[i] ); for ( int i = 1; i <= n; i ++ ) if ( !b[i] ) l[++cntl] = a[i]; else r[++cntr] = L - a[i]; sort ( l + 1, l + 1 + cntl ); sort ( r + 1, r + 1 + cntr ); for ( int i = 1; i <= cntl; i ++ ) ans[i] = l[i]; for ( int i = 1; i <= cntr; i ++ ) ans[n - i + 1] = r[i]; for ( int i = 1; i <= n; i ++ ) printf ( "%.2lf ", ans[i] ); return 0; }
见8.20校内测试，题目转换一下就一模一样了。
数据比较水，写的$O(nlog_nlog_h)$完全够了。
二分最小值，$check$的时候贪心修改区间，我用的线段树，判断一下就好了。实际上差分复杂度更优。写线段树的时候无聊写了区间求和？？
#include<iostream> #include<cstdio> #include<algorithm> #define LL long long using namespace std; int n, K; LL T, a[100005]; LL TR[400005], tag[400005], vc[100005]; void update ( int nd ) { TR[nd] = TR[nd << 1] + TR[nd << 1 | 1]; } void push_down ( int nd, int l, int r ) { if ( tag[nd] ) { int mid = ( l + r ) >> 1; TR[nd << 1] += tag[nd] * ( mid - l + 1 ); TR[nd << 1 | 1] += tag[nd] * ( r - mid ); tag[nd << 1] += tag[nd]; tag[nd << 1 | 1] += tag[nd]; tag[nd] = 0; } } void build ( int nd, int l, int r ) { TR[nd] = 0; tag[nd] = 0; if ( l == r ) { TR[nd] = a[vc[l]]; 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 L, int R, LL d ) { if ( l >= L && r <= R ) { TR[nd] += ( r - l + 1 ) * d; tag[nd] += d; return ; } push_down ( nd, l, r ); int mid = ( l + r ) >> 1; if ( L <= mid ) add ( nd << 1, l, mid, L, R, d ); if ( R > mid ) add ( nd << 1 | 1, mid + 1, r, L, R, d ); update ( nd ); } LL query ( int nd, int l, int r, int pos ) { if ( l == r ) return TR[nd]; push_down ( nd, l, r ); int mid = ( l + r ) >> 1; if ( pos <= mid ) return query ( nd << 1, l, mid, pos ); else return query ( nd << 1 | 1, mid + 1, r, pos ); } bool check ( LL mid ) { int tot = 0; LL sum = 0; for ( int i = 1; i <= n; i ++ ) if ( a[i] < mid ) vc[++tot] = i; build ( 1, 1, tot ); vc[++tot] = 0x7f7f7f7f7f7f7f; for ( int i = 1; i < tot; i ++ ) { LL now = query ( 1, 1, tot - 1, i ); if ( now >= mid ) continue; if ( mid - now + sum > T ) { sum = T + 1; break; } int to = vc[i] + K - 1; int pos = upper_bound ( vc + 1, vc + 1 + tot, to ) - vc - 1; add ( 1, 1, tot - 1, i, pos, mid - now ); sum += mid - now; } if ( sum <= T ) return 1; return 0; } LL MI = 0x3f3f3f3f, MA; LL erfen ( ) { LL l = MI, r = MA + T, ans; while ( l <= r ) { int mid = ( l + r ) >> 1; if ( check ( mid ) ) l = mid + 1, ans = mid; else r = mid - 1; } return ans; } int main ( ) { freopen ( "watering.in", "r", stdin ); freopen ( "watering.out", "w", stdout ); scanf ( "%d%d%I64d", &n, &K, &T ); for ( int i = 1; i <= n; i ++ ) scanf ( "%I64d", &a[i] ), MI = min ( MI, a[i] ), MA = max ( MA, a[i] ); LL ans = erfen ( ); printf ( "%I64d", ans ); return 0; }