您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

蓝桥杯算法训练 礼物 C++详解

资源限制

时间限制: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<=10^12,每个石子的重量小于等于10^9,且非负


这道题一定要注意数据的范围

 

看到题目第一个想法就是循环套循环

#include<iostream>
using namespace std;
 
int main() {
	int N;
	long long S;
	cin >> N >> S;
	int *arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	int ans = 0;
	long long weight1 = 0;
	long long weight2 = 0;
	for (int j = 0; j < N; j++) {
		//cout << "第j个数" << j << endl;
		for (int k = 1; k <= (N - j) / 2; k++) {
			weight1 = 0;
			weight2 = 0;
			//cout << "第j个数后可以有K个,k=" << k << endl;
			for (int i = 0; i < k; i++) {
				weight1 += *(arr + i+j);
				weight2 += *(arr + i + k + j);
				
			}
			//cout << "W1=" << weight1 ;
			//cout << ";W2=" << weight2 << endl;
			if (weight1 <= S && weight2 <= S) {
				ans = max(ans, k);
				//cout << "ans=" << ans << endl;
			}
			else {
				break;
			}
		}
	}

	cout << 2 * ans;

	return 0;
}

但是运行超时,就改进了一下,但是只有90分

#include<iostream>
using namespace std;
const int Max = 1e6 + 3;
int main() {
	int N;
	long long S;
	cin >> N >> S;
	int* arr = new int[N];
	long long sum[Max] ;
	cin >> arr[0];
	sum[0] = arr[0];
	for (int i = 1; i < N; i++) {
		cin >> arr[i];
		sum[i] = sum[i - 1] + arr[i];

	}
	int ans = 0;
	for (int j = 0; j < N; j++) {
		//cout << "第j个数" << j << endl;
		for (int k = ans; k <= (N - j) / 2; k++) {

			//cout << "W1=" << weight1 ;
			//cout << ";W2=" << weight2 << endl;
			if (sum[j + k] - sum[j] <= S && sum[j + 2 * k] - sum[j + k] <= S) {
				//cout << "W1=" << sum[j + k] - sum[j];
				//cout << ";W2=" << sum[j + 2 * k] - sum[j + k] << endl;
				ans = max(ans, k);
				//cout << "ans=" << ans << endl;
			}
			else {
				break;
			}
		}
	}
	cout << 2 * ans;
	return 0;
}

最后就去网上看了一下别人的代码,发现大多数都是用二分法做的

#include<iostream>
using namespace std;
const int Max = 1e6 + 10;
long long sum[Max];
int weight[Max];
long long s;
int n;
bool fun(int k) {
	for (int i = k; i <= n - k; i++) {
		if (sum[i] - sum[i - k] <= s && sum[i + k] - sum[i] <= s)
        //当i=k时,计算的是0~2k;当i=n-k时,计算的是n-2k~n
			return true;
	}
	return false;
}
int main() {	
	cin >> n >> s;
	sum[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> weight[i];
		sum[i] = sum[i - 1] + weight[i];
	}
	int left = 1;
	int right = n / 2;
    //这里right=n也可以
	int k = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (fun(mid)) {
			left = mid + 1;
			k = mid;
		}
		else {
			right = mid - 1;
		}
	}
	cout << 2 * k << endl;
	return 0;
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进