当前位置：首页 > news >正文

牛客小白月赛99（上）

news 2025/5/15 15:14:14

材料打印

题目描述

运行代码

#include<iostream>
using namespace std;
int main(){int T;cin>>T;while(T--){
long long int a,b,x,y;cin>>a>>b>>x>>y;if(x<=y){cout<<a*x+b*y<<endl;}else{cout<<a*y+b*y<<endl;}}return 0;
}

代码思路

一、整体思路

首先从输入中获取测试数据的组数 T。
对于每组测试数据，分别读取 a（既可以黑白打印也可以彩印的页数）、b（必须彩印的页数）、x（黑白打印一页的价格）、y（彩色打印一页的价格）。
比较黑白打印价格 x 和彩色打印价格 y 的大小，以确定对于既可以黑白打印也可以彩印的那部分 a 页如何选择打印方式，从而使得总花费最小。
最后输出每组测试数据的最小花费。

二、具体原理

输入数据部分
- 通过 cin>>T 读取测试数据组数 T。
- 在循环中，使用 cin>>a>>b>>x>>y 依次读取每组测试数据中的四个整数，分别代表可黑白或彩印的页数 a、必须彩印的页数 b、黑白打印一页的价格 x 和彩色打印一页的价格 y。
计算最小花费部分
- 如果黑白打印价格 x 小于等于彩色打印价格 y，那么对于既可以黑白打印也可以彩印的 a 页选择黑白打印，花费为 a*x，而必须彩印的 b 页花费为 b*y，总花费为 a*x + b*y，所以输出 a*x+b*y。
- 如果黑白打印价格 x 大于彩色打印价格 y，那么对于既可以黑白打印也可以彩印的 a 页选择彩色打印，此时这部分的花费为 a*y，再加上必须彩印的 b 页花费 b*y，总花费为 a*y+b*y，输出 a*y+b*y。

多米诺骨牌

题目描述

运行代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>using namespace std;typedef long long LL;
typedef pair<int, int> PII;int main() {int _;cin >> _;while (_--) {int n, m;cin >> n >> m;vector<PII> p(n + 1);for (int i = 1; i <= n; ++i) cin >> p[i].first;for (int i = 1; i <= n; ++i) cin >> p[i].second;sort(p.begin() + 1, p.begin() + n + 1, [](PII a, PII b) {return a.second < b.second;});int ans = 0;int mx = p[1].second;int now = p[1].first;int pu = 1;priority_queue<int> pq;for (int i = 2; i <= n; ++i) {if (p[i].second <= mx + now) {++pu;if (mx + now < p[i].first + p[i].second) {mx = p[i].second;now = p[i].first;}} else {pq.push(pu);pu = 1;mx = p[i].second;now = p[i].first;}}pq.push(pu);while (pq.size() && m--) {ans += pq.top();pq.pop();}cout << ans << '\n';}return 0;
}

代码思路

一、整体思路

首先从输入中获取测试数据的组数 T。
对于每组测试数据，读取骨牌总数 n 和最多可推倒的骨牌数 m，以及各个骨牌的高度和位置信息。
对骨牌按照位置进行排序，然后通过遍历骨牌，利用优先队列（堆）来统计连续倒塌的骨牌数量，并在最多可推倒 m 张骨牌的限制下，计算出最多会有多少张骨牌倒塌。

二、具体原理

输入数据部分
- 通过 cin >> _ 读取测试数据组数 T，并在循环中处理每组数据。
- 对于每组数据，使用 cin >> n >> m 读取骨牌总数 n 和最多可推倒骨牌数 m。
- 接着使用两个循环分别读取骨牌的高度和位置信息，存储在 vector<PII> p(n + 1) 中，其中 PII 是 pair<int, int> 的别名，表示一个包含骨牌高度和位置的对。
处理数据部分
- 首先对骨牌按照位置进行排序，使用自定义的比较函数 [](PII a, PII b) { return a.second < b.second; }，确保位置较小的骨牌排在前面。
- 初始化一些变量，如 ans 用于记录最终的倒塌骨牌总数，mx 记录当前连续倒塌骨牌中最右边骨牌的位置，now 记录当前连续倒塌骨牌中最右边骨牌的高度加上其位置，pu 记录当前连续倒塌的骨牌数量。
- 然后遍历排序后的骨牌：如果当前骨牌的位置在已倒塌骨牌的范围内（即 p[i].second <= mx + now），则增加连续倒塌的骨牌数量 pu，并更新 mx 和 now。如果当前骨牌的位置不在已倒塌骨牌的范围内，则将当前的连续倒塌骨牌数量 pu 放入优先队列（堆）pq 中，重置 pu、mx 和 now。
- 遍历完成后，将最后一组连续倒塌的骨牌数量也放入优先队列。
计算最多倒塌骨牌数部分
- 当优先队列非空且还有可推倒的骨牌数 m 时，从优先队列中取出最大的连续倒塌骨牌数量，累加到 ans 中，并减少可推倒的骨牌数 m。
- 最后输出 ans，即最多会有多少张骨牌倒塌。

自爆机器人

题目描述

运行代码


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e5 + 7, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m, t, a[N];
vector<int> v;
bool f[N];void solve() {v.clear();cin >> n >> m >> t;for (int i = 0; i <= t; i++) f[i] = false;f[n] = true;for (int i = 1; i <= m; i++) cin >> a[i];sort(a + 1, a + 1 + m);for (int i = 1; i < m; i++) v.push_back(a[i + 1] - a[i]);sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());int ans = 0;for (int i = n; i <= t; i++) {if (!f[i]) continue;ans = i;for (auto x: v) {if (i + 2 * x > t) break;f[i + 2 * x] = true;}}cout << ans << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int tc = 1;cin >> tc;while (tc--) solve();return 0;
}

代码思路

一、整体思路

首先从输入中获取测试数据的组数 T。
对于每组测试数据，读取怪物的坐标 n、可建造或摧毁墙壁的坐标数 m、最大起爆时间 t，以及可建造或摧毁墙壁的坐标数组 a。
对可建造或摧毁墙壁的坐标进行排序和去重处理，得到不同的墙壁间隔距离集合 v。
从怪物的位置开始，向最大起爆时间方向遍历，利用动态规划的思想，通过已知可达位置推导出新的可达位置，最终找到在最大起爆时间内能够到达的最大坐标，即对怪物造成的最大伤害。

二、具体原理

输入数据部分
- 通过 cin >> tc 读取测试数据组数 T，并在循环中处理每组数据。
- 对于每组数据，使用 cin >> n >> m >> t 读取怪物的坐标 n、可建造或摧毁墙壁的坐标数 m、最大起爆时间 t。
- 接着使用循环读取可建造或摧毁墙壁的坐标，存储在数组 a 中。
预处理部分
- 对可建造或摧毁墙壁的坐标进行排序，使用 sort(a + 1, a + 1 + m)。
- 计算相邻墙壁之间的间隔距离，存储在向量 v 中，并对 v 进行去重处理，使用 sort(v.begin(), v.end()) 和 v.erase(unique(v.begin(), v.end()), v.end())。
计算最大伤害部分
- 初始化一个布尔数组 f，表示在某个时间点是否可达，初始时只有怪物的位置在时间 n 时可达，即 f[n] = true。
- 从怪物的位置开始向最大起爆时间方向遍历，对于每个可达的位置 i，如果 i 大于最大起爆时间 t，则跳出循环。
- 如果 f[i] 为 false，表示在时间 i 不可达，继续下一个位置的判断。
- 如果 f[i] 为 true，表示在时间 i 可达，更新最大伤害 ans 为当前可达的最大时间 i。
- 对于每个可达位置 i，遍历不同的墙壁间隔距离集合 v，如果 i + 2 * x 超过最大起爆时间 t，则跳出循环，否则将 f[i + 2 * x] 设为 true，表示在时间 i + 2 * x 也可达。
输出结果部分最终输出最大伤害 ans，即对怪物造成的最大伤害。