A.小田的01变换

---

难度：⭐

思路

有2种情况：

（1）0和1的个数不相等。一次操作即可满足要求。

（2）0和1的个数相等，需要先选择一个0和1的个数不相等的区间（可以证明一定有这个区间）变换，再进行整体变换。二次操作即可满足要求。

如果$n<3$,还要特判一下。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int a[2];
int main(){
    freopen("change.in", "r", stdin);
    freopen("change.out", "w", stdout);
    int n;
    cin>>n;
    cin>>s;
    if(n==1){
        cout<<0;
        return 0;
    }else if(n==2){
        if(s[0]==s[1]){
            cout<<0;
        }else{
            cout<<-1;
        }
        return 0;
    }
    for(int i=0;i<s.size();i++){
        a[s[i]-'0']++;
    }
    if(a[0]==0||a[1]==0){
        cout<<0;
    }else if(a[0]>a[1]||a[1]>a[0]){
        cout<<1;
    }else{
        cout<<2;
    }
    return 0;
}

要点

无

---

B.小田滑雪

---

难度：⭐

思路

本题最大的难点就是你不知道明天和意外时间失误和路程失误哪个先来。所以我们需要两个vector来分别存储时间失误和路程失误，排序后遍历，比较当前的两个vector的元素，通过公式转换，用一个time变量求出答案即可。

代码

using namespace std;
vector<int> vt;
vector<int> vd;
int main(){
    freopen("snow.in", "r", stdin);
    freopen("snow.out", "w", stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        char c;
        int x;
        cin>>c>>x;
        if(c=='T'){
            vt.push_back(x);
        }else{
            vd.push_back(x); 
        }
    }
    double time=0;
    double place=0;
    int it=0,id=0;
    double s=1;
    sort(vt.begin(),vt.end());
    sort(vd.begin(),vd.end());
    vt.push_back(2e9);
    vd.push_back(2e9);
    double td;
    while(it<vt.size()-1||id<vd.size()-1){
        int t=vt[it];
        int d=vd[id];
        td=1/s;
        s++;
        double d2=place+(t-time)*td;
        if(d2<d){
            time=t;
            place=d2;
            it++;
        }else{
            time=time+(d-place)/td;
            place=d;
            id++;
        }
    }
    time+=(1000-place)*s;
    cout<<(long long)(time+0.5);
    return 0;
}

要点

• 只推出了转换公式，没有想到用vector存储遍历📄

---