题面

题意:田忌和国王有n匹马,马的速度互不相同。比赛规则是双方每次必须派出最快的马,并且每匹马只能被派出一次。速度高的获胜。 由于田忌马太菜了,国王允许田忌和自己换最多k匹马(这2k匹马由田忌决定) 问田忌最多赢多少次。

m组询问,$n,m\le 10^5$

最多200组数据,输入文件大小不超过8MB,2s。

显然每次交换一定是用自己最差的换国王最好的。

假算法:二分+主席树

对于第k强的马,在一次次交换后田忌这边这匹马的速度只会越来越快,国王那边只会越来越慢。

二分第几次之后这个第k强的马能赢。显然第x次交换后,田忌的马是田忌原来前n-x快的和国王前x快的,其它是国王的,这个第k强可以用主席树。

时间复杂度$O(n \log ^2 n)$ 需要4.4s。

真算法 贪心+Two Pointers

输入已经按速度降序排序了...

对于田忌的每匹马,可以计算出至少后移到哪里能赢对面的马。认为对面有一匹马(第n+1匹)速度为0。

这个可以直接Two-Pointers O(n)解决。

考虑每一次交换,把自己最差一匹马放到对面,可以认为是把对面的其它马排名提高,把对面最强一匹放到自己这边,可以认为是把自己其它马排名降低。

什么?插中间怎么办?

以把自己的放对面为例,其它马显然都能赢这匹马,放对面后,这匹马都不可能赢,比它差的也一样,所以放最后面也一样。

那就相当于把每匹马位置后移两次。所以最少次数就是最少右移的位数除2上取整。

然后

什么?n+1匹是啥意思?

如果你后移到了第n+1匹,说明你碰到了本来比你差换过去的....那显然能赢。

继续移更会赢,所以就是可以直接桶排前缀和。

时间复杂度$O(n)$

/*
Author: CNYALI_LK
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
int a[204847],b[204847],cnt[204847];
int main(){
#ifdef cnyali_lk
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
#endif
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;++i)b[i]=read();
        b[n+1]=0;
        for(int i=1;i<=n;++i)a[i]=read();
        int j=n+1;
        for(int i=0;i<=n;++i)cnt[i]=0;
        for(int i=n;i;--i){
            while(j>i && b[j-1]<a[i])--j;
            ++cnt[(j-i+1)/2];
        }
        for(int i=1;i<=n;++i)cnt[i]+=cnt[i-1];
        for(;m;--m){
            printf("%d\n",cnt[read()]);
        }
    }
    return 0;
}

标签: 贪心, two-pointers

添加新评论