蓝桥——第 3 场 小白入门赛（A-D)

---

一、题目

A.召唤神坤

基本思路：

• 贪心， 使结果最大，希望两边w[i],w[k]是较大的，中间w[j]是较小的

代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 2e6+10;
int n,a[N],b[N];void solve(){cin>>n;repn(i,1,n) cin>>a[i];//贪心， 使结果最大，希望两边w[i],w[k]是较大的，中间w[j]是较小的//先算出并保存第i个元素右边的最大值 for(int i=n;i;i--) b[i]=max(b[i+1],a[i]);
//	for(int i=n;i;i--) cout<<b[i]<<' ';
//	cout<<endl;int res=0,maxn=a[1];repn(i,2,n){res=max(res,(maxn+b[i+1])/a[i]);//枚举a[i]，取结果较大值 maxn=max(maxn,a[i]);//更新i左边的最大值 }cout<<res;
}signed main(){
//	IOS;int T=1;
//	cin>>T;while(T--){solve();}return 0;
}

B.聪明的交换策略

基本思路：

• 这些盒子最后的状态一定是左边都是1右边都是0，或者右边都是1左边都是0。
• 我们不妨将1都移动到左边或者将1都移动右边，去两者花费次数较小的即为最小交换次数。

代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 1e5+10;
int n;void solve(){cin>>n;string s;cin>>s; s=" "+s;//将所有的'1'向左移和向右移，取两者花费较小的//当然这里的移动不是真的交换位置，而是模拟移动的过程 int ans=1e15,l=1,r=n,res=0;//ans一定要足够大！！！血的教训，比赛时调了半天才发现是这里的错误T_T //l表示左边已经确定位置的元素，每移动一个元素l++。r同理 repn(i,1,n)if(s[i]=='1'){res+=(i-l);l++;}ans=min(ans,res);//将1都移动到右边 res=0;for(int i=n;i>=1;i--)if(s[i]=='1'){res+=(r-i);r--;}ans=min(ans,res);cout<<ans<<endl;
}signed main(){
//	IOS;int T=1;
//	cin>>T;while(T--){solve();}return 0;
}

C.怪兽突击

基本思路：

• 贪心的思想，我们取前i个元素，剩下的取k-i个前i个元素中的b的最小值 。这样就能找到所有情况，取较小值即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 1e6+10;
int a[N],b[N];void solve(){int n,k,ans=1e15,minn=1e15,res=0;cin>>n>>k;repn(i,1,n)  cin>>a[i];repn(i,1,n)  cin>>b[i],b[i]+=a[i];//答案一定在取前i个元素，剩下的取k-i个前i个元素中的b的最小值 repn(i,1,min(k,n)){res+=a[i];minn=min(minn,b[i]);//每次保存前面的最小值 ans=min(ans,res+(k-i)*minn);//取前i个元素a1~an，剩下的k-i次取最小值 
//		cout<<minn<<' '<<res<<' '<<ans<<endl;}cout<<ans<<endl;
}signed main(){
//	IOS;int T=1;
//	cin>>T;while(T--){solve();}return 0;
}

D.蓝桥快打

基本思路

• 找出多方需要多少次打败自己，记住要向上取整，这里用来向上取整函数ceil();

代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 1e5+10;
int a,b,c;void solve(){cin>>a>>b>>c;int k=ceil(1.0*a/c);//对方需要多少次打败自己 int res=ceil(1.0*b/k);//自己以最小的攻击力打对方多少次能打败对面 cout<<res<<endl;
}signed main(){
//	IOS;int T=1;cin>>T;while(T--){solve();}return 0;
}