P3105 [USACO14OPEN]Fair Photography S

是个汉子 · 2020-10-20 10:43:50 · 题解

原题

Solution1

考虑如果白牛不能变花牛

如何迅速统计区间牛的数目——利用前缀和统计，设每个牛的 v=1 ，求 sum_i=\sum_{j=1}^iv_j

那么如何迅速判断是否满足白牛数=花牛数——不妨设白牛的 v=1 ，花牛的 v=-1 ，那么区间 (l,r) 满足条件就是 sum_r-sum_{l-1}=0

此时开一个 map 统计 pre_{sum_i} ， pre_i 代表 i 这个值第一次出现的地方， O(n) 扫描取 max\{pos_i-pos{_{pre_{sum_i}}}\}

现在取消限制，白牛可以变花牛

那么区间满足的条件就得发生变化： sum_r-sum_{l-1}\equiv 0\pmod 2

说人话就是花牛和白牛一一配对后，剩下的白牛需要为偶数，这样才能保证将刚好一半的白牛转化成花牛，满足条件

此时如何统计答案呢？我们不能用 O(n^2) 去枚举→_→

因为上面用是 O(n) 扫描，下面不能更劣，所以也考虑扫描。（~~这理由好迷，性感理解~~）

分类讨论一下对于不同的 sum 怎么统计答案

当 sum_i<0 时，需要找一个 j 满足 sum_i-sum_j\geq0(j<i) 。

显然可得 sum_j=sum_i 时最优，因为 sum_i-sum_j>0 意味着还剩下几只白牛，但再加几只花牛总比白牛变花牛优(ง •_•)ง

然后用有限制时的 map 法
当 sum_i\geq 0 时，奇偶还得分开想

时间复杂度： O(n\log n) 排序 + O(n) 扫描

细节：1.因为我们的 pos_i 是从坐标轴的 1 开始的，所以求 sum_i>0 且为偶数的区间长度时答案应该是 pos_i-pos_1 ，奇数同理。2.记得排序，输入不保证有序。

Code1

#include<bits/stdc++.h>

using namespace std;
const int N=100010;
struct node{
    int pos;
    int v;
}cow[N];
int sum[N],ans;
int n;
char op[2];
map<int,int> pre;

inline bool cmp(node a,node y){
    return a.pos<y.pos;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%s",&cow[i].pos,op);
        if(op[0]=='W') cow[i].v=1;
        else cow[i].v=-1;
    }
    sort(cow+1,cow+n+1,cmp);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+cow[i].v;
        if(!pre[sum[i]]&&sum[i]<0) pre[sum[i]]=i;
        else if(sum[i]<0) ans=max(ans,cow[i].pos-cow[pre[sum[i]]].pos);
        if(sum[i]%2==0&&sum[i]>=0) ans=max(ans,cow[i].pos-cow[1].pos);
        else if(sum[i]>=0) ans=max(ans,cow[i].pos-cow[2].pos);
    }
    printf("%d\n",ans);
    return 0;
}

你以为真的结束了吗？

不瞎细心的人会发现我上面写的是Solution1，所以现在是Solution2

Solution2

受机房奆佬ql12345指点此题可以用二分

预处理和Solution1的一样

剩下的就是二分区间长度，然后 O(n) 扫描是否存在满足题目条件的区间长度。

时间复杂度： O(n\log n)

Code2

#include<bits/stdc++.h>

using namespace std;
const int N=100010;
int n;
int sum[N],ans;
struct node{
    int pos;
    int v;
}cow[N];
char op[2];

inline bool cmp(node a,node y){
    return a.pos<y.pos;
}

inline bool check(int x){
    int r=0;
    for(int l=1;l<=n;l++){
        while(cow[r].pos-cow[l].pos<x&&r<n) r++;
        if(cow[r].pos-cow[l].pos<x) 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++){
        scanf("%d%s",&cow[i].pos,op);
        if(op[0]=='W') cow[i].v=1;
        else cow[i].v=-1;
    }
    sort(cow+1,cow+n+1,cmp);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+cow[i].v;
    int l=0,r=1e9+1;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%d\n",l);
    return 0;
}

真的结束了^_^