A - Linear Keyboard
题目:
我们将26个字母按照一定的顺序排列,现在输入一个单词s,在录入一个单词时我们需要逐个连续键入其所有字母,在两个键之间移动手所需的时间等于这些键位置差的绝对值,求确定输入单词s需要多长时间。
思路:
首先记录字母顺序,之后将单词s的每个字符的字母顺序对应的位置做差,记录他们的绝对值就可以了。
AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[30];
int main()
{
int t;
cin>>t;
while(t--)
{
char c;
string s;
int num,ans=0;
for(int i=1;i<=26;i++)
{
cin>>c;
a[int(c-'a')]=i;
}
cin>>s;
num=a[int(s[0]-'a')];
for(int i=0;i<s.size();i++)
{
ans+=abs(num-a[int(s[i]-'a')]);
num=a[int(s[i]-'a')];
}
cout<<ans<<endl;
}
return 0;
}
C - Minimum Extraction
题目:
给定一个大小为n的数组,我们有一个‘最小提取’操作:
我们删除数组里最小的元素,之后从每个剩余的元素减去这个最小的元素。
求在对数组应用几个(可能为零)最小提取操作后,找到数组的最小元素可以具有的最大值。
思路:
我们将数组从小到大排序后,所有的操作就都可以从头直接开始了,我们知道数组里所有的元素同时减去一个最小的元素时数组里的元素的差是不变的,那么我们就直接比较所有相邻元素的差值就可以得出答案了。
AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,ans;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
ans=a[0];
for(int i=1;i<n;i++)
{
ans=max(ans,a[i]-a[i-1]);
}
cout<<ans<<endl;
}
return 0;
}