蓝桥杯算法训练ALGO-1003——礼物

2022/1/8 17:04:47

本文主要是介绍蓝桥杯算法训练ALGO-1003——礼物,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题描述

资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
  JiaoShou在爱琳大陆的旅行完毕,即将回家,为了纪念这次旅行,他决定带回一些礼物给好朋友。
  在走出了怪物森林以后,JiaoShou看到了排成一排的N个石子。
  这些石子很漂亮,JiaoShou决定以此为礼物。
  但是这N个石子被施加了一种特殊的魔法。
  如果要取走石子,必须按照以下的规则去取。
  每次必须取连续的2*K个石子,并且满足前K个石子的重量和小于等于S,后K个石子的重量和小于等于S。
  由于时间紧迫,Jiaoshou只能取一次。
  现在JiaoShou找到了聪明的你,问他最多可以带走多少个石子。
输入格式
  第一行两个整数N、S。
  第二行N个整数,用空格隔开,表示每个石子的重量。
输出格式
  第一行输出一个数表示JiaoShou最多能取走多少个石子。
样列输入
  8 3
  1 1 1 1 1 1 1 1
样列输出
  6
样列解释
  任意选择连续的6个1即可。
数据规模和约定
  对于20%的数据:N<=1000
  对于70%的数据:N<=100,000
  对于100%的数据:N<=1000,000,S<=1012,每个石子的重量小于等于109,且非负

想法思路

想法是用i、j来依次遍历,i为前k1个小于S的石头首指针,j为后k2个小于S的石头的首指针,最后取k1和k2的最小值
代码如下:

#include<iostream>
using namespace std;
int main()
{
	long long N, S, maxk = 0;
	cin >> N >> S;
	int* W = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> W[i];
	}
	for (int i = 0; i < N; i++)
	{
		long long k1 = 0, k2 = 0;
		long long weight1 = 0, weight2 = 0;
		int j, k;
		for (j = i; j < N; j++)
		{
			weight1 += W[j];
			k1++;
			if (weight1 > S)
			{
				k1--;
				break;
			}
		}
		for (k = j; k < N; k++)
		{
			weight2 += W[k];
			k2++;
			if (weight2 > S)
			{
				k2--;
				break;
			}
		}
		maxk = max(max(k1, k2) / 2, maxk);
		maxk = max(min(k1, k2), maxk);
	}
	cout << 2 * maxk << endl;
	return 0;
}

上述代码只能得20分,很明显第2、3中样例都过不了,会超时,就只能想办法改进,很容易想到我们每次遍历获取和值时很耗费时间,而且很明显与前一个有重复的地方,就可以开一个数组来做前缀和。
并且转变了想法,不采用遍历,采用二分查找找符合S的区间,果然问题豁然开朗了
二分法一般适用于所找的值在一个区间

代码改进

这里数组从1开始是为了方便之后对于求mid前多少个和,因为初始化将Sum[0]初始化为0
那么前mid个数之和(包括i)可以直接表示为
Sum[i]-Sum[i-mid]
i后mid个数之和可以表示为
S[mid+i]-S[i]

#include<iostream>
#include<string.h>
using namespace std;
int check(long long mid,long long N,long long S,long long *Sum)
{
	for (int i = mid; i <= N - mid; i++)
	{
		if (Sum[i] - Sum[i - mid] <= S && Sum[i + mid] - Sum[i] <= S)
		{
			return 1;
		}
	}
	return 0;
}
int main()
{
	long long N, S;
	cin >> N >> S;
	long long* W = new long long[N+1];
	long long* Sum = new long long[N+1];//前缀和
	memset(W, 0, sizeof(W));
	memset(Sum, 0, sizeof(Sum));
	for (int i = 1; i <= N; i++)
	{
		cin >> W[i];
		Sum[i] = Sum[i - 1] + W[i];
			
	}
	long long l = 1, r = N;
	while (l < r)
	{
		long long mid = (l + r + 1) >> 1;
		if (check(mid, N, S, Sum))
		{
			l = mid;
		}
		else
		{
			r = mid - 1;
		}
	}
	cout << 2 * l << endl;
	return 0;
}
/*
8 3
1 1 1 1 1 1 1 1

8 3
1 2 3 4 5 6 7 8

*/

这个题真的困扰我很久。。。。可能是我太菜了



这篇关于蓝桥杯算法训练ALGO-1003——礼物的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程