数据结构算法（思维+最大公约数）_C/C++

数据结构算法（思维+最大公约数）

原题链接：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; }