牛客算法周周练11 A 模拟 E 贪心

78 阅读 0 评论 52 点赞

我是靠谱客的博主酷酷皮卡丘，最近开发中收集的这篇文章主要介绍牛客算法周周练11 A 模拟 E 贪心，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://ac.nowcoder.com/acm/contest/6046/A
来源：牛客网

题目描述
众所周知,SD省有一个可爱的妹子,叫做rqy(rqy天下第一可爱!不接受反驳,抱走rqy~),她经常(雾)和一个叫做clccle的蒟蒻一起刷题,但是因为clccle太弱了,所以说她会跳过难度较高的题目,同时，如果clccle的时间不足以切掉当前这道简单题，那么她同时也会跳过这道简单题目，相对的,rqy要花掉两倍的时间去切掉一道难度较高的题目,但如果时间不够用，她会跳过这道题目，但是有一个特殊规定,因为她们两个人都非常懒,所以她们只会按给定的顺序刷,现在两人的刷题列表是一样的,请求出在给定时间里clccle和rqy各最多能刷多少道题目。

输入描述:
第一行,两个整数n,t,表示有n道题目,给定的时间为t

第二行两个整数a,b 分别表示clccle所认为的难度较高和rqy认为的难度较高

接下来两行,每行n个数字第一行表示切题所需的时间，第二行表示题目的难度
输出描述:
输出两个整数,分别表示clccle和rqy的切题数
示例1
输入
复制
2 100
6 10
100 10
7 5
输出
复制
1 1
说明
clccle会跳过第一道题去切第二道题,而rqy会把时间都花在第一题上，P.s.100 10指的是两道题目所需的时间 7 5指的是题目的难度
备注:
难度较高为大于等于给定难度(>=)

1<=n<=100000, 1<=a,b<=1e9

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100005;
typedef long long ll;
struct node
{
   int t, ha;
} e[maxn];
int main()
{
   int n, t;
   cin >> n >> t;
   ll a, b;
   cin >> a >> b;
   ll temp = t;
   ll res1 = 0, res2 = 0;
   for (int i = 0; i < n; i++)
      cin >> e[i].t;
   for (int i = 0; i < n; i++)
      cin >> e[i].ha;
   for (int i = 0; i < n; i++)
   {
      if (temp < e[i].t || e[i].ha >= a)
         continue;
      temp -= e[i].t;
      res1++;
   }
   temp = t;
   for (int i = 0; i < n; i++)
   {
      if (e[i].ha >= b)
      {
         if (e[i].t * 2 > temp)
            continue;
         res2++;
         temp -= e[i].t * 2;
         continue;
      }
      if (e[i].t > temp)
         continue;
      res2++;
      temp -= e[i].t;
   }
   cout << res1 << " " << res2 << endl;

   return 0;
}

链接：https://ac.nowcoder.com/acm/contest/6046/E
来源：牛客网

题目描述
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 n 的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是 hi 。
在搭建开始之前，没有任何积木（可以看成 n 块高度为 0 的积木）。接下来每次操作，小朋友们可以选择一段连续区间 [l, r] ，然后将第第 L 块到第 R 块之间（含第 L 块和第 R 块）所有积木的高度分别增加 1 。

小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

输入描述:
包含两行，第一行包含一个整数 n ，表示大厦的宽度。
第二行包含 n 个整数，第i个整数为 hi
输出描述:
建造所需的最少操作数。
示例1
输入
复制
5
2 3 4 1 2
输出
复制
5
说明
其中一种可行的最佳方案，依次选择[1,5] [1,3] [2,3] [3,3] [5,5]
备注:
对于 30% 的数据，有 1 ≤ n ≤ 10 ；
对于 70% 的数据，有 1 ≤ n ≤ 1000 ；
对于 100% 的数据，有 1 ≤ n ≤ 100000,0 ≤ hi≤ 10000 。

#include <iostream>
using namespace std;
int main()
{
   int n, ans = 0;
   cin >> n;
   int s, num = 0;
   for (int i = 0; i < n; i++)
   {
      cin >> s;
      if (s > num)
      {
         ans += (s - num);
         num = s;
      }
      else
         num = s;
   }
   cout << ans << endl;
   return 0;
}