【C++笔试强训】如何成为算法糕手Day3

小文要打代码

发布于 2024-10-16 15:23:17

770

发布于 2024-10-16 15:23:17

文章被收录于专栏：C++学习历程

第一题：除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;
}

学习编程就得循环渐进，扎实基础，勿在浮沙筑高台

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-09-25，如有侵权请联系 cloudcommunity@tencent.com 删除

指针