Codeforces 988E. Divisibility by 25

发布时间：2020-12-14 04:47:31 所属栏目：大数据来源：网络整理

导读：解题思路：只有尾数为25,50,75,00的数才可能是25的倍数。对字符串做4次处理，以25为例。 a. 将字符串中的最后一个5移到最后一位。计算交换次数。（如果没有找到5，则不可能凑出25，考虑50、75、00） b. 字符串已经改变，将此时最后一个2移到倒数第二位。计

解题思路：

只有尾数为25,50,75,00的数才可能是25的倍数。
对字符串做4次处理，以25为例。
a. 将字符串中的最后一个5移到最后一位。计算交换次数。（如果没有找到5，则不可能凑出25，考虑50、75、00） b. 字符串已经改变，将此时最后一个2移到倒数第二位。计算交换次数。（如果没有找到2，则也不可能凑出25，考虑50、75、00）
c. 将除了最后两位之外的第一个非0的数字移到首位，计算交换次数。（如果找不到除了最后两位之外的非0数字，则不可能凑出25，考虑50、75、00）

注意：

我的WA点：

输入25
输出0

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int solve(string s,char c1,char c2){
// cout << s << endl;
    int len = s.length()-1;
    int ans = 0;
    int flag = false;
    for(int i = 0;s[i]; ++i){
        if(s[i] == c2){
            flag = true;
            for(int j = i;j > 0; j--){
                swap(s[j],s[j-1]);
                ans++;
            }
            break;
        }
    }
// cout << ans << endl;
    if(!flag) return -1;
    flag = false;
    for(int i = 1;s[i]; ++i){
        if(s[i] == c1){
            flag = true;
            for(int j = i;j > 1; j--){
                swap(s[j],s[j-1]);
                ans++;
            }
            break;
        }
    }
    if(!flag) return -1;
    if(len == 1) return ans;
    int con = -1;
    for(int i = len;i > 1; --i){
        if(s[i] != '0'){
            con = i;
            break;
        }
    }
    if(con == -1){
        return -1;
    }else{
        return ans+len-con;
    }
}

int main(){
    ios::sync_with_stdio(false);
    string s;
    while(cin >> s){
        reverse(s.begin(),s.end());
        int ans = INT_MAX;
        int t;
        t = solve(s,'2','5');
    // cout << t << endl;
        if(t != -1){
            ans = min(ans,t);
        }
        t = solve(s,'5','0'); // cout << t << endl;
        if(t != -1){
            ans = min(ans,'7','5'); // cout << t << endl;
        if(t != -1){
            ans = min(ans,'0',t);
        }
        if(ans == INT_MAX) ans = -1;
        cout << ans << endl;
    } 
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

Codeforces 988E. Divisibility by 25

解题思路：

注意：