牛客小白月赛85

第一题-ACCEPT

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

小马是一名算法竞赛爱好者，他认为算法竞赛中表示答案正确的单词 ACCEPT 能给他带来好运，碰巧今天英语课上他得到了一串由 n个大写字母组成的字符串。他想知道，如果他可以将这串字符串以任意顺序进行重新排列，字符串中最多能出现多少个连续的 ACCEPT ？

思路：

就是统计里面的组成该单词的个数，看是否能不能构成，有一个需要注意的地方是这个单词的C是2个，所以在比较各自的次数时，和C比比交时，C的次数的除以2，找到他们的最小值

代码：

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int i;
        char arr[n];
        map<char,int>h;
        for(i=0;i<n;i++){
            cin>>arr[i];
            h[arr[i]]++;
        }
        int ans;
        ans=min(h['C']/2,min(h['A'],min(h['E'],min(h['P'],h['T']))));
        cout<<ans<<endl;
    }
}

第二题：

在一个神奇的国度，有一条一望无际的阶梯。

每层阶梯上都趴着若干只青蛙，具体来说第 ii 层阶梯上有 ii 只青蛙。单身狗喷先生看到了这些青蛙，他想把前 xx 层阶梯（含）上的所有青蛙两两凑成一对。很明显并不是所有的 xx 都能满足这个条件，因为青蛙总数可能为奇数，此时一定有一只青蛙落单。

喷先生并不想看到有青蛙落单，所以他想让你回答一下，将 x 从小到大排序，第 n个满足上述条件（即两两凑对不会出现落单青蛙）的 x 值应该是多少？

思路：

这道题大概思路是就是看1~n什么时候是偶数，题目给出第几次对应是什么时候

首先1~n是奇偶交替的，第n次，如果n为奇数，则为台阶数2*n+1

如果n为偶数则为2*n

代码：

#include<iostream>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    cin>>n;
    ll arr[n];
    ll i,sum=0,count=0;
    if(n%2==0) cout<<2*n; //偶数
    else  cout<<2*n+1;
//     cout<<i;
//     cout<<sum;
}

第三题：得分显示

题目：链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

小菜鸡今天在打某款 ingteresting 的游戏。每当他通关游戏的某一关卡，该关卡的累计得分值就会增加 x\mathrm{x}x。由于 x是一个正实数，因此存在累计得分值不为整数的情况。但是该游戏的累计得分值只能显示整数部分，于是小菜鸡突发奇想，就有了下面的题。

已知小菜鸡共通关该关卡 n次，依次给出小菜鸡每次通过关卡后，该关卡显示的累计得分值（即累计得分值的整数部分），请求出单次通过该关卡所增加的得分值 x 最大为多少？

思路：

其实这道题的思路得认真看一下样例，最大的每次得分是第几次累计得分+1再除以次数，然后都得满足，所以得在他们之间求最小值

代码：

#include<iostream>
using namespace std;
typedef long long ll;
double max1(double a,double b){
    if(a>=b) return a;
    else     return b;
}
int main(){
      ll n;
      cin>>n;
      ll arr[n],i;
    for(i=0;i<n;i++){
        cin>>arr[i];
    }
    double  ans=0;
        ans=arr[0]+1;
        for(i=1;i<n;i++){
            ans=min(ans,(double)(arr[i]+1)/(double)(i+1));
        }
    printf("%.10lf",ans);
    }
  
    

第四题：

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

代码：

void solve()
{
    cin>>n>>m;
    vector<int>a(n);
    ll s=0;
    for(int i=0;i<n;i++)
        cin>>a[i],s+=a[i];
    if(s<m){
        printf("%d\n",n-1);
        return;
    }
    ll sum=0,now=m;
    for(int i=0;i<n;i++){
        if(a[i]){
            sum+=a[i];
            now-=a[i];
            if(now<=0){
                puts("NO");
                return;
            }
        } else if(s-sum<m){
            printf("%lld\n",n+sum-1);
            return;
        }else{
            now=m;
        }
    }
}