作为xxnn晚会的宣传题,请ZH安排一下宣传费用
题目描述
心心廿廿晚会就要开始啦,作为软件学院光辉美丽的化身,春天与喜悦之神,光的拟人化,过去一切沉沦与虚伪的终结者,未来美好与正义的开启者--Alvin辉(朱辉上仙) 他有着旋转乾坤的能力,在晚会的抽奖栏目上,他轻敲响指就可以抽中所有的奖品,有一天他找到了某楠,说出了一个谜语,如果猜对了的话就能把大奖抱回家(不存在的)。
谜语是这样的:
有一连串无序的小写字母,某楠需要交换序列中相邻的两个元素。使得原序列变成不上升序列的最少的交换次数,就是谜底了。
输入
多组数据。
第一行为一个整数$n$,表示序列长度($0
第二行为$n$个字母,表示序列中每个元素。
输出
对于每组数据,输出一行,为谜底,结果对1000000007取模
输入样例
4
a d c e
4
a a a a
输出样例
5
0
题目考点
归并排序呀 以前做过类似的鸭
为什么大家不会读入鸭
#include
#include
#define ll long long
using namespace std;
const int maxn=1000005;
//下面就是 归并排序求逆序对 的过程
char a[maxn],r[maxn];
int n;
ll ans=0;//ans作为全局变量,记录逆序对的数量;
void msort(int s,int t)
{
if(s==t)
return ;
int mid=(s+t)>>1;
msort(s,mid),msort(mid+1,t);//→→→→→→→递归的体现
//在这插入
int i=s,j=mid+1,k=s;
while(i<=mid&&j<=t)
if(a[i]>=a[j])
r[k++]=a[i++];//先赋值再+1
else
r[k++]=a[j++],ans=((ll)mid-i+1+1000000007+ans)%1000000007;//可以理解为上面的数学归纳吧qaq;最重要的部分
while(i<=mid)
r[k]=a[i],k++,i++;
while(j<=t)
r[k]=a[j],k++,j++;
for(int i=s; i<=t; i++)
a[i]=r[i];//复制回a数组中
}
int main()
{
while(cin>>n)
{
ans = 0;
for(int i=1; i<=n; i++)
cin>>a[i];
msort(1,n);//从1到n将a数组排序;
cout<endl;
}
return 0;
}
还有一种读入方法
scanf("%c",&ch);
if(ch<='z'&&ch>='a')
a[i++]=ch;
还有一种读入方法
scanf("%s",ss);
a[i]=ss[0];
怎么就不会读入呢???