【8.30校内测试】【找规律模拟】【DP】【二分+贪心】

对于和规律或者数学有关的题真的束手无策啊QAQ

首先发现两个性质：

1、不管中间怎么碰撞，所有蚂蚁的相对位置不会改变，即后面的蚂蚁不会超过前面的蚂蚁或者落后更后面的蚂蚁。

2、因为所有蚂蚁速度一样，不管标号的话两只蚂蚁的碰撞相当于直接互相穿过，所以最初有多少蚂蚁方向向左，最后就有多少蚂蚁从左落下，向右同理。

总结一下又可以发现，比如有$cntl$只蚂蚁最初向左，$cntr$只蚂蚁最初向右，那么最后就是原位置的左边连续$cntl$只从左落下，原位置右边连续$cntr$只从右落下。我们将所有方向向左和向右的蚂蚁落下的时间分别排序，和原序列上一一对应即可。

#include<iostream>

#include<cstdio>

#include<algorithm>

#define LL long long

using namespace std;

int n, b[], cntl, cntr;

LL a[], L;

double ans[], l[], r[];

int main ( ) {

    freopen ( "ant.in", "r", stdin );

    freopen ( "ant.out", "w", stdout );

    scanf ( "%I64d%d", &L, &n );

    for ( int i = ; i <= n; i ++ )    scanf ( "%I64d", &a[i] );

    for ( int i = ; i <= n; i ++ )    scanf ( "%d", &b[i] );

    for ( int i = ; i <= n; i ++ )

        if ( !b[i] )

            l[++cntl] = a[i];

        else r[++cntr] = L - a[i];

    sort ( l + , l +  + cntl );

    sort ( r + , r +  + cntr );

    for ( int i = ; i <= cntl; i ++ )

        ans[i] = l[i];

    for ( int i = ; i <= cntr; i ++ )

        ans[n - i + ] = r[i];

    for ( int i = ; i <= n; i ++ )

        printf ( "%.2lf ", ans[i] );

    return ;

}

见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[];

LL TR[], tag[], vc[];

void update ( int nd ) {

    TR[nd] = TR[nd << ] + TR[nd <<  | ];

}

void push_down ( int nd, int l, int r ) {

    if ( tag[nd] ) {

        int mid = ( l + r ) >> ;

        TR[nd << ] += tag[nd] * ( mid - l +  );

        TR[nd <<  | ] += tag[nd] * ( r - mid );

        tag[nd << ] += tag[nd];

        tag[nd <<  | ] += tag[nd];

        tag[nd] = ;

    }

}

void build ( int nd, int l, int r ) {

    TR[nd] = ; tag[nd] = ;

    if ( l == r ) {

        TR[nd] = a[vc[l]];

        return ;

    }

    int mid = ( l + r ) >> ;

    build ( nd << , l, mid );

    build ( nd <<  | , mid + , 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 +  ) * d;

        tag[nd] += d;

        return ;

    }

    push_down ( nd, l, r );

    int mid = ( l + r ) >> ;

    if ( L <= mid ) add ( nd << , l, mid, L, R, d );

    if ( R > mid ) add ( nd <<  | , mid + , 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 ) >> ;

    if ( pos <= mid ) return query ( nd << , l, mid, pos );

    else return query ( nd <<  | , mid + , r, pos );

}

bool check ( LL mid ) {

    int tot = ; LL sum = ;

    for ( int i = ; i <= n; i ++ )

        if ( a[i] < mid ) vc[++tot] = i;

    build ( , , tot );

    vc[++tot] = 0x7f7f7f7f7f7f7f;

    for ( int i = ; i < tot; i ++ ) {

        LL now = query ( , , tot - , i );

        if ( now >= mid ) continue;

        if ( mid - now + sum > T ) { sum = T + ; break; }

        int to = vc[i] + K - ;

        int pos = upper_bound ( vc + , vc +  + tot, to ) - vc - ;

        add ( , , tot - , i, pos, mid - now );

        sum += mid - now;

    }

    if ( sum <= T ) return ;

    return ;

}

LL MI = 0x3f3f3f3f, MA;

LL erfen ( ) {

    LL l = MI, r = MA + T, ans;

    while ( l <= r ) {

        int mid = ( l + r ) >> ;

        if ( check ( mid ) ) l = mid + , ans = mid;

        else r = mid - ;

    }

    return ans;

}

int main ( ) {

    freopen ( "watering.in", "r", stdin );

    freopen ( "watering.out", "w", stdout );

    scanf ( "%d%d%I64d", &n, &K, &T );

    for ( int i = ; i <= n; i ++ )    scanf ( "%I64d", &a[i] ), MI = min ( MI, a[i] ), MA = max ( MA, a[i] );

    LL ans = erfen ( );

    printf ( "%I64d", ans );

    return ;

}

巴特西

【8.30校内测试】【找规律模拟】【DP】【二分+贪心】

最新文章

热门文章