题解 P3105 【[USACO14OPEN]公平的摄影Fair Photography】

ysj1173886760 · 2018-11-01 07:18:37 · 题解

很明显的二分了吧

其实是我不会写dp也看不懂题解里dalao的做法QAQ

单调性还是比较显然的

二分一个长度，若存在大于这个长度且满足条件的，说明这个长度可行，否则不可行。

即白牛为1，花牛为-1.

然后离散化一下，再处理一下前缀和。

如果是2的倍数的非负整数，说明满足条件，每次O(n)扫描一遍就行了。

复杂度nlogn

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=1e5+10;

int n;
int sum[maxn];
struct cow
{
    int x,op;
}a[maxn];

bool cmp(const cow &a,const cow &b)
{
    return a.x<b.x;
}
bool check(int x)
{
    int r=0;
    for(int l=1;l<=n;l++)//枚举左端点 
    {                   //每个点最多成为左端点一次，右端点一次，所以check一次的复杂度就是O(n)的 
        while(a[r].x-a[l].x<x&&r<n)r++;//找到合法的右端点 
        if(a[r].x-a[l].x<x)break;       //找不到说明后面的也找不到，及时break 
        if(sum[r]-sum[l-1]>=0&&(sum[r]-sum[l-1])%2==0)return true;//满足条件就返回 
    }
    return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        char op[2];
        scanf("%d %s",&a[i].x,op);
        if(op[0]=='W')a[i].op=1;
        else a[i].op=-1;
    }
    sort(a+1,a+1+n,cmp);//离散一下 
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].op;//处理前缀和 
    int lb=0,ub=1e9+1;//设置上边界和下边界，注意左闭右开区间，所以右端点+1 
    while(ub-lb>1)
    {
        int mid=(lb+ub)>>1;
        if(check(mid))lb=mid;
        else ub=mid;
    }
    cout<<lb;
    return 0;
}