【C++笔试强训】如何成为算法糕手Day3
学习编程就得循环渐进，扎实基础，勿在浮沙筑高台
循环渐进Forward-CSDN博客
目录
循环渐进Forward-CSDN博客
第一题：除2！
第二题：dd爱框框
第三题：简写单词
第一题：除2！
牛客网做题链接：除2！ (nowcoder.com)
思路：模拟+贪心+优先队列
利用优先队列将最大数当作大根，每次将最大的数进行判断，使其满足次数不超过k次。
本题能用贪心是因为每一部最优解都能成为全局的最优解。
//除2！
typedef long long ll;
ll n, k;
priority_queue <ll>q;
int main()
{
cin >> n >> k;
ll sum = 0, x;
while (n--)
{
cin >> x;
sum += x;
if (x % 2 == 0)
{
q.push(x);
}
}
while (q.size() && k--)
{
ll t = q.top() / 2;
q.pop();
sum -= t;
if (t % 2 == 0)
{
q.push(t);
}
}
cout << sum;
return 0;
}第二题：dd爱框框
牛客网做题链接：F-dd爱框框_牛客小白月赛34 (nowcoder.com)
思路：本题有两种解法，一是暴力循环解法，但是时间复杂度会爆炸因此不建议用。二是滑动窗口法。我使用滑动窗口（同向双指针）法解本题。
首先分为四个步骤，一进窗口，二判断值是否满足，三更新结果，四出窗口。
一：设置right右指针先进行移动，配合left左指针进行窗口判断。
二：利用sum数组判断数组内数值是否超过n。
三：当left+right长度小于retlen长度时更新结果
四：sum-=left出窗口
//dd爱框框
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 (retLeft + retRight + 1 < retLen)
{
retLeft = left;
retRight = right;
retLen = retRight - retLeft + 1;
}
sum -= arr[left];
}
}
cout << retLeft << "" << retRight << endl;
return 0;
}第三题：简写单词
牛客网做题链接：简写单词_牛客题霸_牛客网 (nowcoder.com)
思路：这题属实是简单，简单模拟题考察的是对代码的掌握能力。
//简写单词
int main()
{
string s;
while (cin >> s)
{
if (s[0] >= 'a' && s[0] <= 'z')
{
cout << (char)s[0] - 32;
}
else {
cout << s[0];
}
}
return 0;
}学习编程就得循环渐进，扎实基础，勿在浮沙筑高台