题解：P9046 [PA2021] Pandemia

· · 题解

思路

观察到初始有疫情的所有城市会把所有初始没有疫情的 城市分割为若干个区间。

怎么隔离

对于一个区间 [l,r]，有两种情况：

l=1 或 r=n

则此时可以花费一天来将不为 1 或 n 的一个端点处打疫苗来将答案减少 r-l+1。

1<l\le r<n

则此时又有两种情况：

r-l+1\le 2

此时只能将两个端点之一花费一天打疫苗，让另一个端点牺牲。

r-l+1>2

此时可以花费一天时间将其中一个端点打疫苗。

由于在给一个端点打完疫苗后区间全部被感染所需的时间会由 (r-l+1)\div 2 变为 r-l+1，所以由下文结论可得，最优策略为在下一天将另外一个端点往内一个城市处（原端点已被感染）打疫苗。

我们可以将这种操作称为一次“隔离”。

隔离什么

在不打疫苗的情况下，对于一个区间 [l,r]，其在时刻 t 对答案的贡献有两种情况：

l=1 或 r=n

当 t \le r-l+1 时，贡献为 1，否则贡献为 0。

1<l \le r<n

当 t \le (r-l+1)\div 2 时，贡献为 2，当 t+0.5=(r-l+1)\div 2 时，贡献为 1，否则贡献为 0。

观察可发现，在 r-l+1 值越小时，其贡献越容易变为 0。由于题目需求答案最小值，所以可以得出最优策略：优先隔离长度（既 r-l+1）最大的区间，放弃长度较小的区间。

但是，这样做有一个小问题：l=1 或 r=n 的区间的长度缩减速度更慢，所以应将所有区间按全部被感染所需时间从大到小排序，然后依次隔离。

记得特判没有任何城市初始时被感染或全部城市初始时已被感染的情况。

AC CODE

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int n,m;
string s;

struct seg{
    int l,r,t;
};vector<seg> e;

const bool cmp(const seg& a,const seg& b){
    return a.t>b.t;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        e=vector<seg>();
        cin>>n;
        cin>>s;
        int cnt1=0;
        for(int i=0;i<n;++i){
            cnt1+=(s[i]=='1');
        }if(!cnt1){
            cout<<"0\n";
            continue;
        }else if(cnt1==n){
            cout<<n<<'\n';
            continue;
        }
        int curlen=0;
        if(s[0]=='0') ++curlen;
        for(int i=1;i<n;++i){
            if(s[i]=='1'){
                if(curlen){
                    e.push_back({i-curlen,i-1,(i==curlen?curlen*2:curlen)});
                }curlen=0;
            }else{
                ++curlen;
            }
        }if(curlen){
            e.push_back({n-curlen,n-1,curlen*2});
        }sort(e.begin(),e.end(),cmp);
        m=e.size();

        int curt=0;
        int curin=0;
        int ans=0;
        while(curt*2<e[curin].t){
            //cout<<e[curin].l<<' '<<e[curin].r<<' '<<e[curin].t<<endl;
            if(e[curin].l==0 || e[curin].r==n-1){
                ans+=e[curin].r-e[curin].l-curt+1;
                ++curt;
            }else{
                if(curt*2+2>=e[curin].t){
                    ++ans;
                    ++curt;
                }else{
                    ans+=e[curin].r-e[curin].l-curt*2-1+1;
                    curt+=2;
                }
            }++curin;
            if(curin>=m){
                break;
            }
        }//cout<<e[curin].l<<' '<<e[curin].r<<' '<<e[curin].t<<endl;
        cout<<n-ans<<'\n';
    }return 0;
} C++