原题链接:https://codeforces.com/problemset/problem/1216/D
PS:此题为改编题,我按照改编题的题意来写的,和cf原题是一样的。
题意:给定n中血液的剩余存量,且血液剩余存量不会相等,Eily每次回偷喝k cc的血量,问你Eily偷喝血液的最少可能次数和对应的k值。
解题思路:这个问题中我们主要是求最少可能次数,所有的血液存量一开始是相同的,后来变为我们给定的n个血液剩余存量,所以我们先要判断Eily最少喝了多少,有了最少才能进行下一步。那么很明显,我们就是要找血液剩余存量中的最大值,并认为它即为一开始的血液存量。那么我们再来想想k,我们要让k最大,这样才能让喝的次数最少,那么怎么确定k呢?我们应该要仔细想想,每次都是喝k,所以我们每次都是喝k的倍数,那么我们计算最大公约数即可,再比较出最小的,这样才满足。OK,具体看代码。
AC代码:
/* *邮箱:unique_powerhouse@qq.com *blog:https://me.csdn.net/hzf0701 *注:文章若有任何问题请私信我或评论区留言,谢谢支持。 * */ #include<bits/stdc++.h> //POJ不支持 #define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量,a为初始值,n为界限值,递增 #define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量, a为初始值,n为界限值,递减。 #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define fi first #define se second #define mp make_pair using namespace std; const int inf = 0x3f3f3f3f;//无穷大 const int maxn = 1e5;//最大值。 typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; //*******************************分割线,以上为自定义代码模板***************************************// int main(){ //freopen("in.txt", "r", stdin);//提交的时候要注释掉 IOS; string str; int n; while(cin>>n){ cin>>str; int cnt1=0,cnt2=0,cnt=0; if(n%2){ rep(i,0,n-2){ if(str[i]=='a') cnt1++; if(str[i]=='b') cnt2++; if(i%2){ if(cnt1>cnt2){ if(str[i]=='a') str[i]='b'; else{ str[i-1]='b'; } cnt++; } else if(cnt1<cnt2){ if(str[i]=='b') str[i]='a'; else{ str[i-1]='a'; } cnt++; } cnt1=cnt2; } } } else{ rep(i,0,n-1){ if(str[i]=='a') cnt1++; if(str[i]=='b') cnt2++; if(i%2){ if(cnt1>cnt2){ if(str[i]=='a') str[i]='b'; else{ str[i-1]='b'; } cnt++; } else if(cnt1<cnt2){ if(str[i]=='b') str[i]='a'; else{ str[i-1]='a'; } cnt++; } cnt1=cnt2; } } } cout<<cnt<<endl; cout<<str<<endl; } return 0; }
c/c++开发分享数据结构算法(思维+最大公约数)地址:https://blog.csdn.net/hzf0701/article/details/107913875
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598140.html