Codeforces Round 935 (Div. 3)（A,B,C,D,E,F）

比赛链接

阳间场，阴间题，最考阅读理解的一场。题目本身的难度不大。

A. Setting up Camp

题意：

组委会计划在奥运会结束后带领参赛者进行一次徒步旅行。目前，需要携带的帐篷数量正在计算中。据了解，每个帐篷最多可容纳 $3$ 人。在参与者中，有 $a$ 个内向者、 $b$ 个外向者和 $c$ 个共通者：

每个内向的人都想独自住在帐篷里。因此，内向者的帐篷必须只容纳一个人——只有内向者自己。
每个外向的人都想和另外两个人住在一个帐篷里。因此，外向者的帐篷必须正好容纳三个人。
共通者任何选择(独自生活，与另一个人一起生活，或与另外两个人一起生活)都可以接受。

组委会非常尊重每一位参赛者的意愿，所以他们想全部兑现。

告诉我们需要携带的帐篷的最小数量，以便所有参与者可以根据自己的喜好进行住宿。

如果无法以满足所有愿望的方式容纳参与者，则输出 $- 1$ 。

思路：

内向者好说，一人一个帐篷，共通者也好说，哪里不够塞哪里。主要是外向者，因为必须三人一个帐篷的限制，所以我们先给外向者三人分一个帐篷，有可能会剩下不足三人，这时用共通者补上，如果补不上，就无解，否则就有解。

code：

#include <iostream>
#include <cstdio>
using namespace std;

int T,a,b,c;

int main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>c;
		int d=(3-b%3)%3,ans=a+(b+c+2)/3;
		if(d>c)cout<<-1<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}

B. Fireworks

题意：

徒步旅行的其中一天恰逢假期，所以晚上在营地，人们决定安排一场喜庆的烟花表演。为了这个目的，这次远足的组织者购买了两个发射烟花的装置和数量巨大的发射炮弹。两个装置安装后同时打开。

第一个装置打开后每 $a$ 分钟放一次烟花(即启动后 $\cdot a, 3 \cdot a, \dots$ 分钟放一次烟花)。第二个装置打开后每 $b$ 分钟放一次烟花(即发射后 $\cdot b, 3 \cdot b, \dots$ 分钟放一次烟花)。

每个烟花在发射后 $m + 1$ 分钟内在天空中可见，即，如果在安装开启后 $x$ 分钟后发射烟花，则从 $x$ 到 $x + m$ (含)每分钟都可见。如果一个烟花在另一个烟花发射后 $m$ 分钟发射，则两个烟花都将在第 $x + m$ 这一分钟内同时可见。问，在同一时间，天空中最多可以看到多少烟花？

思路：

看似比较麻烦，我们不妨转化一下思路：在某一个时间 $t$ 上看到的所有烟花是前面第 $t-m\sim t$ 时间段上释放的所有烟花。那么问题就转化成了：找一个时间段，长为 $m + 1$ ，使得这个时间段上释放的烟花最多。

如果我们要让一个烟花在一个时间段上释放的次数最多，根据贪心的思想，显然我们时间区间左端点应该选在这个烟花刚刚释放的时候，假如这个烟花释放间隔是 $a$ ，那么这个时间段上烟花会释放 $\left\lfloor\dfrac ma\right\rfloor+1$ 次。

同理，两个烟花也是如此，我们希望区间左端点选在两个烟花同时释放的时候。问题在于这两个烟花存在同时释放的情况的吗？如果两个烟花是倍数关系，那么显然存在，如果不是倍数关系，那么两个数的最小公倍数时刻就是两个烟花同时释放的时刻。因此两个烟花一定存在同时释放的情况。因此两个烟花总的释放次数就是 $\left\lfloor\dfrac ma\right\rfloor+\left\lfloor\dfrac mb\right\rfloor+2$ 。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

int T;
ll a,b,m; 


int main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>m;
		cout<<m/a+m/b+2<<endl;
	}
	return 0;
}

C. Left and Right Houses

题意：

在列托沃村，有 $n$ 栋房屋。村民们决定修一条大路，把村子分成左右两边。每个居民都想住在街道的右边或左边，这被描述为序列 $a_1, a_2, \dots, a_n$ 。其中如果 $a_j = 0$ ，表示第 $j$ 栋房屋的住户想住在街道的左侧，否则 $a_j = 1$ ，表示住户想住在街道右侧。

这条路将从两座房子之间穿过。它左边的房子将被宣布为左边，右边的房子将被宣布为右边。更正式地说，让道路在房屋 $i$ 和 $i + 1$ 之间通过。那么位于 $1$ 和 $i$ 之间的房屋将位于街道的左侧。在 $i + 1$ 和 $n$ 之间的房屋将位于右侧。在这种情况下，道路也可以在第一栋房子之前和最后一栋房子之后通过。整个村庄分别被宣布为右侧或左侧。

为了使设计公平，人们决定铺设这条路，使得村庄两边至少有一半的居民对这一选择感到满意。也就是说，在一边的 $x$ 个居民中，至少有 $\lceil\frac{x}{2}\rceil$ 个应该想住在那一边，其中 $\lceil x \rceil$ 表示实数 $x$ 向上取整数。

在这里插入图片描述

注：在路的左边，将有 $i$ 个房子，在相应的 $a_j$ 中必须至少有 $\lceil\frac{i}{2}\rceil$ 个 $0$ 。在路的右边，将有 $n - i$ 栋房屋，在相应的 $a_j$ 中，必须至少有 $\lceil\frac{n-i}{2}\rceil$ 个 $1$ 。

确定在哪个房屋 $i$ 之后应铺设道路，以满足所描述的条件，并尽可能靠近村庄的中心。形式上说，在所有合适的位置 $i$ 中，最小化 $\left|\frac{n}{2} - i\right|$ 。

如果有多个合适的位置，则输出较小的位置。

思路：

前半部分要求 $0$ 的个数不少于总个数的一半，话句话说就是 $0$ 的个数要多于等于 $1$ ，同理后半部分就是 $1$ 的个数要多于等于 $0$ 。

想要快速求得一个区间 $1$ 的个数和 $0$ 的个数的差值，朴素的想法可以分别处理 $1$ 和 $0$ 的前缀和，不过不用这么麻烦，我们可以把 $1$ 看成 $1$ ，把 $0$ 看成 $- 1$ ，这样跑出来的前缀和直接就是 $1$ 的个数减去 $0$ 的个数的差值。

因为查询很快，只有 $O (1)$ ，我们直接从中间向两边枚举分割线位置，第一个找到的位置就是答案。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=3e5+5;

int T,n;
string str;

int s[maxn];

inline bool check(int x){
	return s[x]-s[0]<=0 && s[n]-s[x]>=0;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>str;
		str=" "+str;
		for(int i=1;i<=n;i++)
			s[i]=s[i-1]+(str[i]=='0'?-1:1);
		
		for(int l=n/2,r=(n+1)/2;l>=0;l--,r++){
			if(check(l)){
				cout<<l<<endl;
				break;
			}
			if(check(r)){
				cout<<r<<endl;
				break;
			}
		}
	}
	return 0;
}

D. Seraphim the Owl

题意：

这些人排成 $n$ 人的队列，从第 $i = 1$ 人开始，向猫头鹰Serafim询问生命的意义。不幸的是，基里尔正忙着为这个问题写传奇，所以他晚到了一会儿，站在队伍的最后，排在第 $n$ 个人的后面。基里尔对这种情况非常不满，所以他决定先贿赂一些人。对于队列中的第 $i$ 个人，Kirill知道两个值： $a_i$ 和 $b_i$ 。

如果此时基里尔站在位置 $i$ ，然后，他可以选择任何位置 $j$ ，使得 $j\lt i$ 与位置 $j$ 的人交换位置。在这种情况下，基里尔将不得不支付他 $a_j$ 个硬币。对于每个 $k$ ，例如 $\lt k \lt i$ ，Kirill必须向位置 $k$ 的人支付 $b_k$ 个硬币。基里尔很节俭，所以他想花尽可能少的硬币，但又不想等太久。所以基里尔希望他能排在前 $m$ 位。

帮助基里尔确定他必须花费的最小硬币数量，以免等待太久。

思路：

假设我们最后停在第 $m$ 位上，那么我们一定需要支付 $a_m$ 。在中间时发现如果一个人的 $b_i$ 比较大，比 $a_i$ 大，那么我们就可以先和这个人交换位置，把这个人的代价从 $b_i$ 换成 $a_i$ ，而其他人不变。所以每个人要么被贿赂 $a_i$ ，要么被贿赂 $b_i$ 。那么我们肯定两者取其小。

因为停在前 $m$ 个位置上都是可行的，所以朴素想法就是枚举停在前面所有位置上时的花费，不过发现只有停到的某个位置 $i$ 上必须支付 $a_i$ 以外，后面 $i+1\sim n$ 的位置的代价都是 $a_j,b_j$ 值取其小值。所以我们从后向前枚举 $i$ ，后面部分的代价是不会变的，直接累加起来即可。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const ll inf=1e18;

int T,n,m;
int a[maxn],b[maxn];

int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)cin>>b[i];
		ll ans=0,minn=inf;
		for(int i=m+1;i<=n;i++)ans+=min(a[i],b[i]);
		for(int i=m;i>=1;i--){
			minn=min(minn,ans+a[i]);
			ans+=min(a[i],b[i]);
		}
		cout<<minn<<endl;
	}
	return 0;
}

E. Binary Search

题意：

安东在徒步旅行中感到无聊，想要解决一些问题。他问基里尔有没有什么新问题，当然，基里尔有一个。给出一个大小为 $n$ 的排列 $p$ 和一个需要查找的数字 $x$ 。

长度为 $n$ 的排列是由从 $1$ 到 $n$ 的 $n$ 个不同整数以任意顺序组成的数组。例如， $[2, 3, 1, 5, 4]$ 是排列，但 $[1, 2, 2]$ 不是排列( $2$ 在数组中出现两次)，并且 $[1, 3, 4]$ 也不是排列( $n = 3$ ，但数组中有 $4$ )。你认为自己是一个很酷的程序员，所以你将使用一种先进的搜索算法——二分查找（binary search）。

但是，您忘记了，二分查找的前提是必须对数组进行排序。不过你没有放弃，决定无论如何都要应用这个算法，为了得到正确的答案，在运行算法之前，您可以执行以下操作不超过 $2$ 次：

选择索引 $i$ ， $j$ ( $1\le i, j \le n$ )并交换位置 $i$ 和 $j$ 处的元素。之后，执行二分查找。

在算法开始时，声明了两个变量 $l = 1$ 和 $r = n + 1$ 。然后执行以下循环：

如果 $r - l = 1$ ，则结束循环。
$\lfloor \frac{r + l}{2} \rfloor$ 。
如果是 $p_m \le x$ ，则分配 $l = m$ ，否则分配 $r = m$ 。

目标是在算法之前重新排列排列中的数字，以便在执行算法之后， $p_l$ 等于 $x$ 。可以证明 $2$ 次操作总是有解的。

思路：

进行一系列手玩之后，发现整个区间的大部分数都是没用的，搜索区间的变化只和一路上 $m$ 指向的数的大小有关系。

而且我们可以得到一个看似没用的结论：所有数只分两种，一种是 $\le x$ 的数，一种是 $\gt x$ 的数。若 $m$ 指向了前者，二分搜索区间就会向右缩小至一半，若 $m$ 指向了后者，二分搜索区间就会向左缩小至一半。

这样的话，我们相同种类的数可以直接相互交换位置，而不会影响到二分搜索的路径。

根据上面得到的两条性质，我们可以将 $x$ 直接交换到最后 $a_l$ 的所在位置上，而整个二分搜索的路径不会发生变化。因为：

$a_l$ 的位置从始至终没有被 $m$ 指向过，这时 $x$ 也肯定不会被指向（如果 $a_l$ 的位置被 $m$ 指向过， $l$ 会一直留在最后一个 $m$ 指向的 $\le x$ 的位置上，这说明 $a_l$ 就被 $m$ 指向过，与上面的假设不符。而如果 $x$ 被指向过，那么它一定是作为 $a_l$ 被指向，就和上面的 $a_l$ 没有被指向的假设冲突了），两个数交换位置也不会影响到二分搜索的路径。
$a_l$ 的位置被 $m$ 指向过，这时 $a_l$ 与 $x$ 是同类数，交换位置不会影响到二分搜索的路径。

所以我们直接模拟一下题目上的二分的过程，将 $x$ 直接交换到最后 $a_l$ 的所在位置上即可。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;

int T,n,x;
int a[maxn];

int main(){
	cin>>T;
	while(T--){
		cin>>n>>x;
		int idx;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]==x)idx=i;
		}
		int l=1,r=n+1,mid;
		while(l+1<r){
			mid=(l+r)>>1;
			if(a[mid]<=x)l=mid;
			else r=mid;
		}
		if(l==idx)printf("0\n");
		else printf("1\n%d %d\n",idx,l);
	}
	return 0;
}

F. Kirill and Mushrooms

题意：

这题面讲的是依托啊！！！😡

营地里的人一睡着，基里尔就偷偷溜出帐篷，去智慧橡树采集蘑菇。据了解，橡树下生长着 $n$ 个蘑菇，每个蘑菇都有魔力 $v_i$ 。

基里尔真的很想从蘑菇中制造出一种具有最大力量的神奇灵丹妙药。仙丹的力量等于使用的蘑菇个数和这些蘑菇中的最小法力值的乘积。

为了准备灵丹妙药，基里尔将采摘一种生长在橡树下的蘑菇。基里尔可以按任何顺序采集蘑菇。然而，事情并没有那么简单。聪明的橡树告诉基里尔从 $1$ 到 $n$ 的数字排列 $p$ 。

如果基里尔选择了 $k$ 个蘑菇，那么第 $p_1, p_2, \dots, p_{k - 1}$ 个蘑菇的魔力将变为 $0$ 。基里尔不能用魔法力量为零的蘑菇来制作仙丹。你的任务是帮助基里尔收集蘑菇，这样他就可以酿造出最大强度的灵丹妙药。

然而，基里尔有点害怕在橡树附近呆太久，所以在所有适合采集蘑菇的选择中，他让你找出蘑菇数量最少的那个。长度为 $n$ 的排列是由 $n$ 个从 $1$ 到 $n$ 的不同整数以任意顺序组成的数组。

例如， $[2, 3, 1, 5, 4]$ 是一个排列，但 $[1, 2, 2]$ 不是一个排列( $2$ 在数组中出现了两次)并且 $[1, 3, 4]$ 也不是排列( $n = 3$ ，但 $4$ 出现在数组中)

思路：

我们蘑菇失效的顺序是 $p_1, p_2, \dots, p_{k - 1}$ ，这样随机失效处理起来比较难受，所以我们把蘑菇按失效顺序排一下序。现在问题就变成了前 $i - 1$ 个蘑菇失效，选择后 $n - i + 1$ 个蘑菇中的 $i$ 个，使得选出的 $i$ 个蘑菇的最小魔力值乘以 $i$ 最大。

我们选出后 $n - i + 1$ 个蘑菇中的 $i$ 个，使得最小魔力值最大，那么我们肯定选魔力值最大的 $i$ 个。动态维护前 $i$ 大个元素，这就比较适合用对顶堆来做。

而每次选完都要删掉第 $i$ 个元素，同时维护住最大的 $i + 1$ 个，再向后走，但是这样会比较麻烦，因为堆没法找到一个具体的元素。所以我们把这个过程反过来，删元素就相当于加元素了，我们加入第 $i$ 个元素，并维护住最大的 $i$ 个元素，更新完答案后，再继续向前走。

不过对顶堆可以优化为一个堆，下面说。

code：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;

int T,n;
int t[maxn],a[maxn];

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>t[i];
		for(int i=1,id;i<=n;i++){
			cin>>id;
			a[i]=t[id];
		}
		
		priority_queue<int> h1;
		priority_queue<int,vector<int>,greater<int> > h2;
		ll ans=0,tot;
		for(int i=n;i>=1;i--){//前i-1个被删掉了 
			h2.push(a[i]);
			if(n-i+1<i)continue;
			while(h2.size()>i){
				h1.push(h2.top());
				h2.pop();
			}
			while(h2.size()<i){
				h2.push(h1.top());
				h1.pop();
			}
			if(ans<=1ll*i*h2.top()){
				ans=1ll*i*h2.top();
				tot=h2.size();
			}
		}
		cout<<ans<<" "<<tot<<endl;
	}
	return 0;
}

发现其实 $h 1$ 这个堆是自始至终没法向 $h 2$ 中加入元素的，因为 $i$ 是逐渐变小的，对应着 $h 2$ 的容量也是变小的，我们把 $a_i$ 先放进 $h 2$ 里，再剔除一部分元素，使得元素剩余总个数缩小到 $i$ ，这就完成了一个浓缩的过程。因为 $h 1$ 存储的都是 $h 2$ 不要的元素，所以 $h 1$ 这个堆是自始至终没法向 $h 2$ 中加入元素的。直接优化掉 $h 1$ 就好了。

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;

int T,n;
int t[maxn],a[maxn];

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>t[i];
		for(int i=1,id;i<=n;i++){
			cin>>id;
			a[i]=t[id];
		}
		
		priority_queue<int,vector<int>,greater<int> > h2;
		ll ans=0,tot;
		for(int i=n;i>=1;i--){//前i-1个被删掉了 
			h2.push(a[i]);
			if(n-i+1<i)continue;
			while(h2.size()>i)h2.pop();
			
			if(ans<=1ll*i*h2.top()){
				ans=1ll*i*h2.top();
				tot=h2.size();
			}
		}
		cout<<ans<<" "<<tot<<endl;
	}
	return 0;
}