从第一步操作可以得到程序的结果与字母的顺序无关,
所以不妨转化为数组z[26][2]来储存a,b字符串字母的数量。
而第二步操作中
如果直接按照题设的步骤来做,
即对a字符串进行“k个相同字母+1”
那么写出的代码会十分繁琐,且不容易打出正确的代码。
所以我们不妨逆向操作
对b字符串进行“k个相同字母-1”
即:z[i][1]-=k; z[i-1][1]+=k;
并从最大的字母z(也就是25(z-97=25))开始进行操作
int i=25; while(i) { ....... z[i][1]-=k; z[i-1][1]+=k; i--; }
为了避免无用的多次循环,我们可以先排除一些可能性
int tot=0,tot1=0;
for(i=0;i<26;i++)
{
tot+=z[i][0]*i;
tot1+=z[i][1]*i;
}
if(tot1<tot||abs(tot1-tot)%k!=0)
{
cout<<"NO"<<endl;
}
下面是代码展示(欢迎批评指正~)
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string.h>
#include <stdlib.h>
using namespace std;
char a[1000005];
char b[1000005];
void solve()
{
int n,k;
int i,i1,i2;
int z[26][2]={0};
cin>>n>>k;
scanf("%s",a);
scanf("%s",b);
for(i=0;i<n;i++)
{
z[a[i]-97][0]++;
z[b[i]-97][1]++;
}
int tot=0,tot1=0;
for(i=0;i<26;i++)
{
tot+=z[i][0]*i;
tot1+=z[i][1]*i;
}
if(tot1<tot||abs(tot1-tot)%k!=0)
{
cout<<"NO"<<endl;
}
else
{
int temp=1;
i=25;
while(i)
{
if(z[i][0]>z[i][1])
{
temp=0;
break;
}
else if(z[i][0]<z[i][1])
{
z[i][1]-=k;
z[i-1][1]+=k;
}
if(z[i][1]<0)
{
temp=0;
break;
}
else if(z[i][0]==z[i][1])
{
i--;
}
}
if(temp==1)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
(本人是最近入坑的萌新,想借此做笔记,欢迎与我交流与讨论~)