链接: https://www.nowcoder.com/acm/contest/121/C
时间限制: C/C++ 1 秒, 其他语言 2 秒
空间限制: C/C++ 131072K, 其他语言 262144K
64bit IO Format: %lld
题目描述
iko 超级超级喜欢吃糖, 有一天 iko 想出去玩, 她计划从 1 点走到 N 点 (按 1,2,3,...,n 的顺序走), 每个点都有一个补给站, 第 i 点的补给站有 a[i] 颗糖, 从 i 点走到 i+1 点会消耗掉 b[i]颗糖, iko 在出游的途中可以选择三个补给站, iko 想知道她走完全程到达 N 点时口袋里最多还能剩下几颗糖(初始时 iko 的口袋里一颗糖都没有).
输入描述:
第一行输入 N(3<=N<=1000)
第二行输入 N 个数代表 a[1].......a[N] (0<=a[i]<=1000 )
第三行输入 N-1 个数代表 b[1]......b[N-1] ( 1<=b[i]<=1000 )
输出描述:
输出一个数字表示 iko 到达 n 点时口袋里最多剩下的糖,
若不能到达 N 点输出 - 1.
示例 1
输入
3 1 3 4 3 4
输出
-1
示例 2
输入
5 3 4 5 2 4 3 2 2 2
输出
3
思路: 虽然你到一地方时不知道该不该捡, 但是归根结底我们是要选在保证不减为负数的情况下选择最大的, 所以可以用一个优先队列将路过的数量都记录下来, 当不够的时候就将从优先队列里面选择
最大的加上, 加到够减为止.
- #include <bits/stdc++.h>
- using namespace std;
- int a[1005];
- int b[1005];
- int main(){
- int n;
- cin>> n;
- for(int i = 0; i <n; i++){
- cin>> a[i];
- }
- for(int i = 0; i <n - 1; i++){
- cin>> b[i];
- }
- priority_queue<int> myq;
- int sum = 0, ct = 0;
- for(int i = 0; i <n - 1; i++){
- myq.push(a[i]);
- // if(sum < b[i]){
- // sum += myq.top(); // 加一次不一定就够了, 但是题目数据可以水过!!!
- // myq.pop();
- // sum -= b[i];
- // ct++;
- // }
- if(sum < b[i]){
- while(sum < b[i]){
- sum += myq.top();
- myq.pop();
- ct++;
- }
- sum -= b[i];
- }
- else{
- sum -= b[i];
- }
- if(ct> 3 || sum < 0){
- cout << "-1" << endl;
- return 0;
- }
- }
- myq.push(a[n - 1]);
- while(ct < 3){
- sum += myq.top();
- myq.pop();
- ct++;
- }
- cout << sum << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2599951.html