AtCoder Beginner Contest 376 题解

AtCoder Beginner Contest 376

A - Candy Button

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve(){
	int n,c;cin>>n>>c;
	int pre=-1;
	int ans=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		if(pre==-1){
			pre=x;
			ans++;
		}
		else if(x-pre>=c){
			pre=x;
			ans++;
		}
	}
	cout<<ans<<endl;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

B - Hands on Ring (Easy)

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n;
bool check(int l,int m,int r){
	return (l<m && m<r);
}
int step(int s,int t,int b){
	if(s==t) return 0;
	if(s>t) t+=n;
	if(check(s,b,t) || check(s,b+n,t)){
		return n-(t-s);
	}
	else return t-s;	
}
void solve(){
	int q;cin>>n>>q;
	int l=0,r=1;
	int ans=0;
	while(q--){
		char op;cin>>op;
		int p;cin>>p;
		p--;
		if(op=='L'){
			ans+=step(l,p,r);
			l=p;
		}
		else{
			ans+=step(r,p,l);
			r=p;
		}
	}
	cout<<ans<<endl;

}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

C - Prepare Another Box

#include<bits/stdc++.h>
#define endl '\n'
#define int long long 
using namespace std;
const int N=2e5+10;
int a[N],b[N],tmp[N];
int n;
bool check(int x){
	for(int i=1;i<=n-1;i++) tmp[i]=b[i];
	tmp[n]=x;
	sort(tmp+1,tmp+n+1);
	for(int i=1;i<=n;i++){
		if(a[i]>tmp[i]) return false;
	}
	return true;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n-1;i++) cin>>b[i];
	sort(a+1,a+n+1);
	int l=0,r=1e9;
	int ans=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	cout<<ans<<endl;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

D - Cycle

解题思路

• 包含点1的最小环，直接从点1开始跑bfs，第一次回到点一时的路径长度即为环的大小

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=2e5+10;
typedef pair<int,int> PII;
bool vis[N];
vector<int> g[N];
void solve(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		g[u].push_back(v);
	}
	queue<PII> q;
	q.push({1,0});
	vis[1]=1;
	int ans=0;
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		auto [u,d]=t;
		for(auto v:g[u]){
			if(v==1){
				ans=d+1;
				cout<<ans<<endl;
				return;
			}
			if(vis[v]) continue;
			vis[v]=1;
			q.push({v,d+1});
		}
	}
	cout<<-1<<endl;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

E - Max × Sum

解题思路

• 枚举ai,只需要维护满足aj<=ai的前k-1小的bj的和，用优先队列简单维护
• 一个trick，可以单独记录id数组，对id数组排序时依赖a,b数组的值，这样就可以不对a,b数组进行改变

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],b[N];
bool cmp(int x,int y){
	return a[x]<a[y];
}
void solve(){
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	vector<int> id(n);
	//iota函数，为区间按顺序加1赋值
	//记录id数组，可以方便排序
	iota(id.begin(),id.end(),1);
	sort(id.begin(),id.end(),cmp);
//	for(auto x:id) cout<<x<<endl;
	priority_queue<int> q;
	int sum=0;
	int ans=1e18;
	for(int i=0;i<n;i++){
		int idx=id[i];
		while(q.size()>k){
			auto t=q.top();
			q.pop();
			sum-=t;
		}
		if(i>=k-1){
			int tmp=0;
			if(i>=k) tmp=q.top();
			else tmp=0; 
			ans=min(ans,a[idx]*(sum-tmp+b[idx]));
		}
		q.push(b[idx]);
		sum+=b[idx];
	}
	cout<<ans<<endl;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}