青岛市程序设计竞赛冲刺④（2022山东省小学组补赛试题）

1.独木桥

原题：

 解题思路：

n个人中，每个人越靠近一个端点，就朝着那个方向走到头，求出最大距离即最大时间

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+5;
int n,L,a[N],ans=0;
int main(){
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	cin>>n>>L;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]=min(a[i],L-a[i]),ans=max(ans,a[i]);
	cout<<ans;
	return 0;
}

2.移动棋子

原题：

解题思路：

分四种情况，分别是1.x<=y   2.x<=-y  3.-x<=y  4.-x<=-y,按情况取最小值即为答案

AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int x,y,ans=INT_MAX;
int main(){
	cin>>x>>y;
	if(x<=y)ans=min(ans,y-x);
	if(x<=-y)ans=min(ans,-y-x+1);
	if(-x<=y)ans=min(ans,y+x+1);
	if(-x<=-y)ans=min(ans,-y+x+2);
	cout<<ans;
	return 0;
}

3.动物园

原题：

解题思路：

求出每种动物在l到i这个区间中出现了多少次，并确定区间，是区间长度最小化，就是答案

AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6+5,M = 2e3+5;
int a[N],b[M],n,m,cot,l=1;
int main(){
	cin>>n>>m;int ans=n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(!b[a[i]])cot++;
		b[a[i]]++;
		if(cot==m){
			for(int j=l;j<=i;j++){
				if(b[a[j]]>1){
					l++;
					b[a[j]]--;
				}else break;
			}
			ans=min(ans,i-l+1);
		}
	}
	cout<<ans*10;
	return 0;
}

4.摧毁

原题：

解题思路：

统计每条卫星轨道上有多少颗卫星，只可能有两种可能，一种是每一颗卫星都被激光武器定点摧毁，需要花费1*SUM_i，另一种是一条轨道上所有的卫星都被轨道武器摧毁，需要花费c，最后累加最小值，即为答案

AC代码：

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define ll long long
using namespace std;
const int N = 1e6+5;
int aSum[N],n,c,T;
int main(){
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	cin>>T;
	while(T--){
		int r=0;
		long long ans=0;
		memset(aSum,0,sizeof(aSum));
		cin>>n>>c;
		for(int i=1,a;i<=n;i++)cin>>a,aSum[a]++,r=max(r,a);
		for(int i=0;i<=r;i++)ans+=min(aSum[i],c);
		cout<<ans<<'\n';
	}
	return 0;
}