Median String 26进制的加和除

题目链接:http://codeforces.com/problemset/problem/1144/E

题意:给两个字符串,第一个字符串小于第二个字符串,求大于等于第一个字符串小于等于第二个字符串的所有字符串的中间的字符串。

思路:一开始我觉得这个题好难啊,如果一个一个求,用for循环求,真的求不出来,但是我看到别人的思路,就觉得很简单,其实可以把字符串看成26进制的数,然后求中位数,再转化为字符串就解决了。

AC代码

#include<iostream>
#include<string>
using namespace std;
const int MAX=2e5+10;
int a[MAX];
string b="abcdefghijklmnopqrstuvwxyz";
int main()
{
    int n;
    cin>>n;
    string s1,s2;
    cin>>s1>>s2;
    int jinwei=0;
    for(int i=n-1;i>=0;i--)
    {
        int sum=jinwei+s1[i]-'a'+s2[i]-'a';
        jinwei=sum/26;
        a[i]=sum;
        if(jinwei>0&&i!=0)a[i]-=26;
    }
    int shengyu=0;
    for(int i=0;i<n;i++)
    {
        int sum=a[i]+shengyu*26;
        a[i]=sum/2;
        shengyu=sum%2;
    }
    for(int i=0;i<n;i++)
    {
        cout<<b[a[i]];
    }
    return 0;
} 

 

上一篇:PAT 甲级 1029 Median (25 分)(思维题,找两个队列的中位数,没想到)*


下一篇:左闭右开线段树 2019牛客多校(第七场)E_Find the median(点代表区间