0928携程笔试题解

游游的字符交换

思路：按题意模拟即可。枚举交换每一对，判断完了再换回来。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int _;
    cin>>_;
    while(_--){
        string s,y;
        cin>>s>>y;
        int n=s.length(),i,j,jud=0;
        for(i=0;i<n;i++){
            for(j=i+1;j<n;j++){
                swap(s[i],s[j]);
                if(s==y)jud=1;
                swap(s[i],s[j]);
            }
        }
        cout<<(jud?"Yes\n":"No\n");
    }
}

233星人

思路：如果不是233的倍数，显然无解。否则可以看成是233乘以一个十进制数，计算数位之和即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int _;
    cin>>_;
    while(_--){
        long long x;cin>>x;
        if(x%233!=0){cout<<-1<<'\n';continue;}
        x/=233;
        int cnt=0;
        while(x)cnt+=x%10,x/=10;
        cout<<cnt<<'\n';
    }
}

数组平均

思路：先将数组排序，选择的元素一定是最小的一些元素和最大的一些元素。枚举选择的区间即可，可以用前缀和或者一边遍历一边维护选择的数之和。

#include <bits/stdc++.h>
using namespace std;
int a[202020];
long long op[202020],ed[202020];
int main() {
    int n,i,j,k;
    cin>>n>>k;
    for(i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    long long s1=0,s2=0;
    for(i=1;i<=n;i++)op[i]=s1+=a[i];
    for(i=n;i>=1;i--)ed[i]=s2+=a[i];
    double mi=1e18;
    for(i=0;i<=k;i++){
        int l=i+1,r=l+(n-k)-1;
        double avg=1.0*(op[i]+ed[r+1])/k;
        mi=min(mi,max(1.0*a[r],avg)-min(1.0*a[l],avg));
    }
    printf("%.7f",mi);
}

游游的k-好数组

思路：首先将数组变成k-好数组，即每个都相等的数都变成这些数的最大值，消耗一定的操作次数。

然后是两种方案：将小于的某个变得更大，或者将大于的某个变得更大。后者比前者需要多变一个数，分别统计可能拿到的最大值即可。

#include<bits/stdc++.h>
using namespace std;
int a[202020],ma[202020];
int main(){
    int _;
    cin>>_;
    while(_--){
        int n,k,x,i,mm=0,mm2=0;
        cin>>n>>k>>x;
        long long sum=0;
        for(i=0;i<k;i++)ma[i]=0;
        for(i=0;i<n;i++){
            cin>>a[i];
            ma[i%k]=max(ma[i%k],a[i]);
            if(i%k<n%k)mm=max(mm,a[i]);
            else mm2=max(mm2,a[i]);
        }
        long long s=0;
        for(i=0;i<n;i++){
            s+=ma[i%k]-a[i];
        }
        if(s>x){cout<<-1<<'\n';continue;}
        x-=s;
        cout<<max(mm+x/(n/k+1),mm2+x/(n/k))<<'\n';
    }
}