【C++】 —— 笔试刷题day_3
刷题_day3
继续加油！！！
一、简写单词
题目链接：简写单词
题目描述
这道题比较简单，题目说的也非常简单明了
输入一行复合词，要求我们输出每个单词的首字母大写。
算法思路
这里我们可以看到输入的复合词中，每一个单词用 隔开；所以我们就可以应该单词应该单词读取（而不是使用getline来读取一行）。
读取到一个单词之后，如果其首字母是大写就直接输出，如果不是就转换成大写再进行输出。
注意：这里如果使用
getline来读取一行，处理起来将会十分的麻烦；极其不推荐
代码实现
#include <iostream>
using namespace std;
int main() {
string str;
while(cin>>str)
{
if(str[0]>='a' && str[0]<='z')
cout<<(char)(str[0]-32);
else
cout<<str[0];
}
return 0;
}
二、DD爱框框
题目链接：DD爱框框
题目描述
输入
n,x，再输入n个数，让我们找到在这个数组中a中找到连续的区间[l，r]，这个区间内的和大于等于x，并且返回长度最小的（如果存在相同长度的，输出l最小的那一个）。
这里需要注意的是
- 这里题目中说的下标是从
1开始的，所以我们最后输出的结果也是下标从1开始对应的下标。- 题目要求长度相同的，返回
l最小的，这里不需要太关注（我们遍历是从左往右的，所以只需要遇到长度最短的再进行更新结果即可）。
算法思路
看到这道题，首先暴力解法，枚举出来所有的连续区间；找到其中大于等于x且长度最小的。
（如果了解过滑动窗口算法的，这道题可以说一眼秒了。
现在来暴力解法进行优化：
对于暴力解法，我们找到满足条件的区间
[l，r]时，我们会执行l++，然后让r再从l开始，寻找满足条件的区间。这样时间复杂度就到达了
O(n^2)；
那该如何遍历呢？
- 这里我们更新完结果并执行完
l++以后，让r保持不动- 如果还是满足条件，就重复上述操作。直到不满足条件
- 再让
r往后遍历即可。
这样r遍历完成以后，我们就遍历结束了。
这里稍微了解一下滑动窗口
- 进窗口
- 更新结果
- 出窗口并更新结果直到不满足条件
这样，我们从始至终都维持了一个窗口
[l，r]，只需要在其右侧进行进窗口，左侧进行出窗口节课；根据题意在需要位置进行更新结果。
代码实现
#include<iostream>
using namespace std;
const int N = 1e8+10;
int arr[N];
int n,x;
int main()
{
cin>>n>>x;
for(int i=1;i<n;i++) cin>>arr[i];
int left =1, right =1;
int ret = n + 1, retLeft = -1, retRight = -1;
int sum = 0;
while(right < n)
{
//入窗口
sum+=arr[right];
//出窗口
while(sum>=x)
{
if(right - left < ret)
{
//更新结果
ret = right -left;
retLeft = left;
retRight = right;
}
sum -= arr[left++];
}
right++;
}
cout<<retLeft<<" "<<retRight<<endl;
return 0;
}
三、除2
题目链接：除2
题目描述
题目要求，在输入的一堆数当中，我们可以对其中的偶数进行
k次/2操作，让数组中的所有数之和尽可能最小。然后让我们求出这个最小的数之和并输出。这里注意观察题目的数值范围，
1<= a <=10^9，1<= n <=100000；我们在定义变量时就不能定义整形，而是long long以免数据超出范围
算法思路
看一下题目这个示例1，我们可以了解到，对一个偶数/2之后的除数如果是偶数，我们还是可以对其进行/2操作的。
看完题目，我们大致可以了解到：题目要求
- 对偶数进行
/2操作，那么奇数我们操作不了，就可以将奇数先加起来。- 对偶数操作之后的除数如果是偶数，我们可以对除数进行
/2操作- 我们需要保证，进行k次
/2操作以后，所以数之后是最小的；那这样我们只需要对最大的偶数进行/2操作就好了这样，我们就可以现将
奇数加起来，然后对偶数进行操作，如果除数是奇数，就可以直接将其加起来；如果是除数是偶数，我们就要将除数放回到偶数堆中，然后接着进行/2操作。
看到这里，我们遇到了一个问题？
如何存放偶数，保证我们每一次都能取到最大的偶数，并且在进行/2操作后，将这个除数放回偶数里面。
这里就要用到一个数据结构，那就是
堆，也就是priority_queue；
那这道题的总体思路就是，将奇数累加起来，让偶数保持一个堆结构来保证我们每一次对偶数的最大值进行操作。
代码实现
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
priority_queue<long long> pq;
long long sum =0;
long long x;
for(int i=0;i<n;i++)
{
cin>>x;
if(x%2==0)//如果输入的是偶数
pq.push(x);
else//输入的是奇数
sum+=x;
}
while(!pq.empty() && k--)
{
x = pq.top();
pq.pop();
x/=2;
if(x%2==0)//除数是偶数
pq.push(x);
else//除数是奇数
sum+=x;
}
while(!pq.empty())
{
sum+=pq.top();
pq.pop();
}
cout<<sum<<endl;
return 0;
}
坚持打卡第3天，继续加油啊！！！