YACS(上海市计算机学会竞赛平台)二星级题单——闯关升级

2023-12-22 10:16:29
题目描述

小爱可以玩两个游戏,每个游戏各有?n?关,每过一关升一级,每关的通关时间是不同的。给定一个整数?t,表示小爱玩游戏的时间,请问她应该如何分配时间,才能让升级的次数达到最大?(不可以跳关)

输入格式

第一行:两个整数?n?和?t;
第二行:n?个整数a[1]?,a[2]?,…,a[n]?,表示第一个游戏每个关卡的通关时间;
第三行:n?个整数?b[1]?,b[2]?,…,b[n]?,表示第二个游戏每个关卡的通关时间。

输出格式

单个整数:表示最多能通过多少关。

数据范围
  • 对于?30% 的数据,1≤n≤20;
  • 对于?60%?的数据,1≤n≤1000;
  • 对于?100%?的数据,1≤n≤100000,1≤t≤1,000,000,000,1≤a[i]?,b[i]?≤10000。
样例数据

输入:

4 22
6 8 10 7?
7 11 9 9

输出:

3

说明:

选择通关6、7、8

主要思想
?1.跳关

如果可以跳关,那么直接两个数组sort一下就OK了,但这题不行。

2.数据

一般人想到的是直接枚举,看每种情况哪种过关最多,直接输出。但这样只能打60%的分,不可取。

那么怎样求和呢?

3.前缀和

运用前缀和可以更快的求出数组的每一元素相加之和。

代码实现
#include <bits/stdc++.h>
using namespace std;
int n, t;
int a[100005], b[100005];
int ans = 0;

int main() {
	cin >> n >> t;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		b[i] += b[i - 1];
	}
	int sheng;//剩余的时间
	int p = n; //b游戏可以过几关
	for (int i = 0; i <= n; i++) { //枚举a游戏通过从0关至n关的情况
		sheng = t - a[i];
		if (sheng < 0)
			break;//处理越界问题
		while (b[p] > sheng) {
			p--;
		}
		ans = max(ans, i + p); //把答案设为最多关数
	}
	cout << ans;
	return 0;
}

文章来源:https://blog.csdn.net/A3024857/article/details/135131186
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。