题目描述
A string ss of length nn , consisting of lowercase letters of the English alphabet, is given.
You must choose some number kk between 00 and nn . Then, you select kk characters of ss and permute them however you want. In this process, the positions of the other n-kn−k characters remain unchanged. You have to perform this operation exactly once.
For example, if s=\texttt{"andrea"}s="andrea" , you can choose the k=4k=4 characters \texttt{"a_d_ea"} and permute them into \texttt{"d_e_aa"} so that after the operation the string becomes \texttt{"dneraa"}"dneraa" .
Determine the minimum kk so that it is possible to sort ss alphabetically (that is, after the operation its characters appear in alphabetical order).
输入格式
The first line contains a single integer tt ( 1 \le t \le 10001≤t≤1000 ) — the number of test cases. Then tt test cases follow.
The first line of each test case contains one integer nn ( 1 \le n \le 401≤n≤40 ) — the length of the string.
The second line of each test case contains the string ss . It is guaranteed that ss contains only lowercase letters of the English alphabet.
输出格式
For each test case, output the minimum kk that allows you to obtain a string sorted alphabetically, through the operation described above.
题意翻译
题目大意：
有 t 组数据，每组数据会给你一个长度为 n 的字符串 s 。
你可以选择 k 个数，并把这 k 个数排序。使字符串 s 最后按照字典序排序。输出 k 的最小值。
输入输出样例
输入 #1复制
4
3
lol
10
codeforces
5
aaaaa
4
dcba
输出 #1复制
2
6
0
4
说明/提示
In the first test case, we can choose the k=2k=2 characters \texttt{"_ol"} and rearrange them as \texttt{"_lo"} (so the resulting string is \texttt{"llo"}"llo" ). It is not possible to sort the string choosing strictly less than 22 characters.
In the second test case, one possible way to sort ss is to consider the k=6k=6 characters \texttt{"_o__force_"} and rearrange them as \texttt{"_c__efoor_"} (so the resulting string is \texttt{"ccdeefoors"}"ccdeefoors" ). One can show that it is not possible to sort the string choosing strictly less than 66 characters.
In the third test case, string ss is already sorted (so we can choose k=0k=0 characters).
In the fourth test case, we can choose all k=4k=4 characters \texttt{"dcba"}"dcba" and reverse the whole string (so the resulting string is \texttt{"abcd"}"abcd" ).
题意，我们可以先把字符串拍好序，然后我们可以在进行比较字符串，找出几个不同。
#include<bits/stdc++.h> using namespace std; int t,n; string s1,s2;//string永远的神 signed main(){ cin>>t; while(t--){ cin>>n>>s1; s2=s1; sort(s2.begin(),s2.begin()+s2.size());//先完整的排一遍序 int ans=0; for(int i=0;i<s2.size();i++)//然后找不同，看有几个 if(s1[i]!=s2[i]) ans++; cout<<ans<<endl; } }//字典序排序
