陕西师范大学第七届程序设计竞赛网络同步赛 C iko和她的糖【贪心/ STL-优先队列/ 从1-N每个点有能量补充，每段有消耗，选三个点剩下最多能量】

时间：2021-06-12 20:38:22

链接：https://www.nowcoder.com/acm/contest/121/C
来源：牛客网

题目描述

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。

输入例子:
3

1 3 4

3 4
输出例子:
-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>

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define rep(i,n,x) for(int i=(x); i<(n); i++)

#define in freopen("in.in","r",stdin)

#define out freopen("out.out","w",stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e18;

const int maxn = 1e3 + ;

const int maxm = 1e6 + ;

const double PI = acos(-1.0);

const double eps = 1e-;

const int dx[] = {-,,,,,,-,-};

const int dy[] = {,,,-,,-,,-};

const int mon[] = {, , , , , , , , , , , , };

const int monn[] = {, , , , , , , , , , , , };

int n,m;

int a[maxm],b[maxm],c[maxm];

priority_queue<int> q;

int main()

{

    int n;

    cin>>n;

    for(int i=;i<n;i++) cin>>a[i];

    for(int i=;i<n-;i++) cin>>b[i];

    int now = , cnt = ;

    for(int i=; i<n; i++){

        q.push(a[i]);

        while(now < b[i]){ //现在拥有的糖果数量小于消耗的

            if (q.empty()) return puts("-1"), ;

            if (cnt == ) return puts("-1"), ;

            now += q.top();

            q.pop();

            cnt++; //次数计数

        }

        if(i<n-) now-=b[i]; 

    }

    while(cnt< && !q.empty()){ //

        now += q.top();

        q.pop();

        cnt++;

    }

    cout<<now<<endl;

}

相关文章