文章目录

  • 一、题目
    • A.召唤神坤
      • 基本思路:
      • 代码
    • B.聪明的交换策略
      • 基本思路:
      • 代码
    • C.怪兽突击
      • 基本思路:
      • 代码
    • D.蓝桥快打
      • 基本思路
      • 代码

一、题目

A.召唤神坤

基本思路:

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

代码

#includeusing 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都移动右边,去两者花费次数较小的即为最小交换次数。

代码

#includeusing 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的最小值 。这样就能找到所有情况,取较小值即可。

代码

#includeusing 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<<' '<}cout<<ans<<endl;}signed main(){//IOS;int T=1;//cin>>T;while(T--){solve();}return 0;}

D.蓝桥快打

基本思路

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

代码

#includeusing 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;}