cfRound935div3--DEFG题解

ps:这场因为精神状态不佳,又C题题意有点绕,卡题了,头晕找不到错.最后做了两题就溜了.狠狠扣90分..

D-Seraphim the Owl

题意:

即选一个位置,使得其满足题意。而且在满足题意的基础上，要靠近中心越好，如果满足题意而且靠近中心的距离一样，那么输出前面那个.

int cnt0[300005]={0};    //要定义在外面，否则会超时....
int cnt1[300005]={0};
void solve(){           //C  细节问题..
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        char x; cin>>x;
        cnt0[i]=0,cnt1[i]=0;
        if(x=='0') cnt0[i]+=cnt0[i-1]+1;        //0左--1右
        else cnt0[i]=cnt0[i-1];
        if(x=='1') cnt1[i]+=cnt1[i-1]+1;
        else cnt1[i]=cnt1[i-1];
    }
    int ans;
    double dis=INT_MAX;
    for(int i=0;i<=n;i++){
        int num1=i/2;
        if(i&1) num1++;
        int num2=(n-i)/2;
        if((n-i)&1) num2++;
        if(cnt0[i]>=num1&&cnt1[n]-cnt1[i]>=num2){
            //第二个条件是cnt1[n]-cnt[i]!! --不是cnt1[n]-cnt[i-1]
            //例如i==2,意思是在2后面插入,那么2是在左边的,不能算在右边..
            if(abs(1.0*n/2.0-i)<dis){
                ans=i;
                dis=abs(1.0*n/2.0-i);
            }
        }
    }
    cout<<ans<<endl;
}

这题的前缀和减法写错了,因为是算挡板后面的1，所以cnt[n]-cnt[i]就是i+1到n的1的个数..

D-Seraphim the Owl

题意:

做法:在[m+1,n]的区间a和b那个小就选那个，因为前面的换位置是没有意义的-可换可不换.那肯定是选小的代价。到了m以及[1-m]区间的换位置才是有意义的.这个时候只需要枚举记录[1-m]哪个位置交换代价最小即可.再加上[m+1,n]的区间的代价.

int a[200005],b[200005];
void solve(){                   //D--贪心--也可以dp
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int ans=0,minn=INT_MAX,cursum=0;
    for(int i=n;i>m;i--) ans+=min(a[i],b[i]);
    for(int i=m;i>=1;i--){
        minn=min(minn,a[i]+cursum);
        cursum+=b[i];
    }
    cout<<ans+minn<<endl;
}

E-Binary Search

题意:

做法:思维题。“意识”到就简单--和最后的pl交换位置即可,因为能成为最后的pl,那么他一定是小于等于k的.因为遇到k也是l=mid,和最后的pl进行交换位置,其他位置保持不动,不会影响到达最后的pl.

或者更容易理解的：因为同一个数组二分算法到达的位置是一样的，那可以把k放到一个不会到达的位置，再把k放到最后的pl.

int arr[200005];
void solve(){                   //E--思维-构造
    // 和最后的pl交换位置即可,因为能成为最后的pl,那么他一定是小于等于k的.因为遇到k也是l=mid,和最后的pl进行交换位置,其他位置保持不动,不会影响到达最后的pl
    int n,k,idxk;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        if(arr[i]==k) idxk=i;
    }
    int l=1,r=n+1;
    while(l+1!=r){
        int mid=(l+r)/2;
        if(arr[mid]<=k) l=mid;
        else r=mid;
    }
    if(l==idxk) cout<<"0\n";
    else cout<<"1\n"<<idxk<<" "<<l<<endl;
}

F-Kirill and Mushrooms