笔试练习day3

感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接
🐒🐒🐒 个人主页
🥸🥸🥸 C语言
🐿️🐿️🐿️ C语言例题
🐣🐣🐣 python
🐓🐓🐓 数据结构C语言
🐔🐔🐔 C++
🐿️🐿️🐿️ 文章链接目录
🏀🏀🏀 笔试练习题

BC149 简写单词

链接添加链接描述

题目解析

这道题就是提取一句话中每个单词的首字母,并且将他们的首字母用大写的形式输出,这里的难点就在于每个单词是通过空格分隔开的,在输入的时候如果用scanf和cin直接输入的话会因为有空格而丢失后面的数据
解决这个难点的第一个方法是用getline输入,getline输入是遇到’\n’才停止,也就是遇到回车键才结束,这样就不会因为有空格而丢失数据了,后面过程就是通过循环去找空格出现的位置,然后空格的下一个位置就是单词的首字母
第二个方法就是用string去解决(这个解法就是通过循环直接往string中输入字符串,然后每次循环输出输入的字符串首字母)

代码

int main()
{
string s;
while(cin>>s)
{if(s[0]<='z'&&s[0]>='a'){s[0]=s[0]-32;}cout<<s[0];
}return 0;
}

dd爱框框

链接dd爱框框

题目解析

这道题的意思是在1到n的区间里我们要求出里面的最小区间,使得区间里的所有数加起来大于或等于x,比如区间[1,5]意思就是从arr[1]开始一直到arr[5]的所有数据,[5,8]就表示从arr[5]到arr[8],需要注意这里的n个数是从1开始的,所以用数组的时候我们要先从1开始输入

解析

我们以图中示例为例

输出3 5表示区间[3,5]中的所有数据加起来大于等于x,且这个区间的长度相比于后面的区间长度来说是最小的

代码

方法一暴力解法

暴力解法就是给一个left和right让right和left相加,当结果大于等于x的时候就记录下来

这里的范围是[1,5],然后left往后移动,之后right=left,然后right往后走

方法二同向双指针(滑动窗口)

这个方法是在方法一的基础上进行优化
比如left在1的时候,范围是[1,5],在这个范围的总和为27,之后left++
但是right是没有必要重新会到left位置再往后去确定范围,因为left在a[1]的时候right在a[5]是刚好满足条件的,那么left++后来到a[2]时[2,5]的所以数总和只会比[1,5]少一个a[1],所以只需要在[1,5]总和减去一个a[1]就可以了

然后判断减去a[1]后[2,5]是否满足>=x的条件
这个方法的流程如下

#include<iostream>
using namespace std;
const int N=1e7+10;
int arr[N];
int n,x;
int main()
{cin>>n>>x;for(int i=1;i<=n;i++)cin>>arr[i];int left=0,right=0,sum=0;int retLen=N,retLeft=-1,retRight=-1;while(right<=n){sum+=arr[right];while(sum>=x){if(right-left+1<retLen){retLeft=left;retRight=right;retLen=right-left+1;}sum-=arr[left++];}right++;}cout<<retLeft<<" "<<retRight<<endl;return 0;
}

这里有一些细节就是我们将N arr[N] n x都定义成全局变量,这样做的好处是有些题可能会封装一些函数,需要传入这些数据,当我们把他定义成全局变量的时候,就可以不用传参了

此外N=1e7+10让N有足够大

内部的while循环是为了让retLen足够小,让减去一次arr[left]的时候,如果sum仍然大于x,那么就继续减,直到刚好小于x

除2!

链接除2!

题目解析

这道题就是每次操作选取最大的偶数进行砍半,使所以数相加最小

解法

模拟+贪心+堆

#include<iostream>
#include<queue>
using namespace std;typedef long long LL;
LL n,k;
priority_queue<LL> heap;
int main()
{cin>>n>>k;LL sum=0,x;while(n--){cin>>x;sum+=x;if(x%2==0)heap.push(x);}while(heap.size()&&k--){LL t=heap.top()/2;heap.pop();sum-=t;if(t%2==0)heap.push(t);}cout<<sum;return 0;
}

需要注意这里k和ai的范围都是[1,10^9],并且n的范围是[1,10 ^5],因为要让n个数累加,最后的结果肯定是超过int的最大值的,所以我们用int类型显然是不行的,因此要用longlont,代码中用typedef将longlong命名为LL

priority_queue heap是一个队优先级队列(堆)

第一个while循环是为了让sum将所以的数都加起来,然后如果有偶数,那么就进入堆中

第二个while循环需要先判断堆中是否有元素,当堆里面什么都没有的时候就没有必要继续进行下去了,并且每次循环要让k–,表示操作次数减1

因为是优先级队列,堆顶元素是最大的数,我们用t保留最大数的一半,然后让堆顶元素出堆,之后让sum减去一半这个最大的数,但是我们并不知道t是否还是偶数(t如果一开始是2,2/2=1就变成了奇数,而t如果是4…这些偶数,4/2=2),所以需要再对t进行判断,如果还是偶数那么就继续入堆,然后重复操作