文章目录
- 一、题目
- 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];for(int i=n;i;i--) b[i]=max(b[i+1],a[i]);int res=0,maxn=a[1];repn(i,2,n){res=max(res,(maxn+b[i+1])/a[i]);maxn=max(maxn,a[i]);}cout<<res;}signed main(){int T=1;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;int ans=1e15,l=1,r=n,res=0;repn(i,1,n)if(s[i]=='1'){res+=(i-l);l++;}ans=min(ans,res);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(){int T=1;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];repn(i,1,min(k,n)){res+=a[i];minn=min(minn,b[i]);ans=min(ans,res+(k-i)*minn);
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(){int T=1;cin>>T;while(T--){solve();}return 0;}