第二题

题目描述

小红很喜欢刷抖音，抖音后台有一个推荐系统，小红向上滑动屏幕时，该推荐系统会计算成显示恰小红的翔视频

用数值量化而言。每个短视频有一个内存占用ai（画质越好的视频内存占用越大），以及该视频可以带给小红愉悦度为bi。

值得注意的是，当小红每次重复易到同一个视频时，观看该视频获得的愉悦度会除以2（向下取整）。例如，若一个视频初始给小红获得的愉悦度为 5，那么第二次小红获得的愉悦度会变成2，第三次为 1，第四次以后再刷到这个视频获得的愉悦度就为0了

小红一共进行了q次刷视频操作。

为了使得手机不卡顿，推荐系统每次会选择一个内存占用不赢于xi的视频。如奥有多个这样的视频，推荐系统会推荐满足条件的播放画质最好的那个视频（即内存占用最高的视频）。如果有多个视频的画质都是最好，那么推荐系统会推荐当前愉悦度最高的视频。

当小红观看完这个视频后，即可获得该视频的愉悦度，请你计算小红剧完所有视频时获得的总愉悦度。

输入

第一行：n个视频，q次刷取；

第二行：n个视频的内存占用；

第三行：n个视频的愉悦度；

第四行：q次刷取的内存额度。

示例

输入

3 4
3 5 1
3 4 2
3 3 6 1

输出

10

说明

第一次刷视频，推荐系统推荐给小红第一个视频。小红获得愉悦度3。第二次刷视频，推荐系统推荐给小红第一个视频。由于是第二次观看，小红获得愉悦度 1。第三次刷视频，推荐系统推荐给小红第二个视频，小红获得输悦度 4。第四次刷视频，推荐系统推荐给小红第三个视频。小红获得愉悦度2。

代码

维护一个map，map的key是视频的大小，map的value是一个priority_queue，包含该大小的所有视频的愉悦度。

#include <iostream>
#include <vector>
#include <map>
#include <queue>

int main() {
  long long n, q;
  cin >> n >> q;
  vector<pair<long long, long long>> vec(n);
  for (long long i = 0; i < n; ++i) {
	cin >> vec[i].first;
  }
  for (long long i = 0; i < n; ++i) {
	cin >> vec[i].second;
  }
  
  map<long long, priority_queue<long long>> videos;
  for (auto& p : vec) {
	videos[p.first].emplace(p.second);
  }
  
  vector<long long> x(q);
  for (long long i = 0; i < q; ++i) {
	cin >> q[i];
  }
  
  long long ans = 0;
  for (long long i = 0; i < q; ++i) {
	auto it = videos.upper_bound(x[i]);
	it--;
	long long cur = it->top();
	ans += cur;
	it->pop();
	it->push(cur / 2);
  }
  
  cout << ans << endl;
}

第三题

描述

小红在玩一个大富贫游戏，游戏的地图为一排房子，从左到右喻马依次从1到n。

每个房子有一个购买价格ai和一个经过它的房租价格bi，当小红经过一个自己没有购买的房子时，她就需要交房租 (已购买的房子则不需要交房租)。

在游戏开始前，小红可以购买任意数量的房子，然后开始游戏。

游戏中，小红会按照一个给定的排列p的顺序依次经过所有的房子（排列p为房子的编号顺序，p的大小为n，即每个房子都会作为一次目标）。

小红每经过一套房子都需要交租金，除非已购买。初始小红在第一个房子的左边，当她按够顺序经过了所有房子后，她会再次移动到第n个房子的右边。

请你计算小红最少的总花费。

输入输出

第一行输入一个整数n，代表房子的总数；
第二行输入一个排列pi，代表小红经过的房子编号；
第三行输入n个整数ai，代表房子的购买价格；
第四行输入n个整数bi，代表房子的房租价格；
保证[1, n]中每个数在p中出现且仅出现一次。

一行一个整数，代表最少的总花费

示例

4
1 3 2 4
5 4 2 4
1 3 1 1

8

游戏开始前买下第二个房子，花费4。
开始游戏时，小红先向右走一步到达1号房子，房租价格为1。
然后向右走2步到达3号房子，当小红经过2号房子时由于2号房子已经购买，则不用交房租。
然后到达3号房子时交房租价格为1。
然后向左走1步到达2号房子，不需要交房租。
然后向右走2步到达4号房子，经过的3号房子和4号房子分别交价格为1的房租。
最后向右离开这个大富翁地图。

代码

差分数组

#include <iosream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> p(n + 2, 0);
  for (int i = 1; i <= n; ++i) cin >> p[i];
  p[n + 1] = n;
  
  vector<int> a(n + 1, 0);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  
  vector<int> b(n + 1, 0);
  for (int i = 1; i <= n; ++i) cin >> b[i];
  
  int pos = 0;
  vector<int> pre(n, 0);
  for (int i = 1; i <= n + 1; ++i) {
	// 向右走
	if (pos <= p[i]) {
	  pre[pos + 1] += 1;
	  pre[p[i] + 1] -= 1;
	}
	// 向左走
	else {
	  pre[pos] -= 1;
	  pre[p[i]] += 1;
	}
	pos = p[i];
  }
  
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
	pre[i] += pre[i - 1];
	ans += min((long long)a[i], (long long)pre[i] * b[i]);
  }
  
  cout << ans << endl;
}