网站建设 网页设计需要技能,西安网站推广都是怎么做的,常德行业网站,wordpress主机 知乎资源限制
内存限制#xff1a;256.0MB C/C时间限制#xff1a;1.0s Java时间限制#xff1a;3.0s Python时间限制#xff1a;5.0s
问题描述 老虎moreD是一个勤于思考的青年#xff0c;线性代数行列式时#xff0c;其定义中提到了逆序数这一概念。不过众所周知我们…资源限制
内存限制256.0MB C/C时间限制1.0s Java时间限制3.0s Python时间限制5.0s
问题描述 老虎moreD是一个勤于思考的青年线性代数行列式时其定义中提到了逆序数这一概念。不过众所周知我们只需要知道逆序数的奇偶性就行了为了防止计算上的失误moreD准备编写一个小程序来判定。只要判断奇偶性就行了哦 另外作为一个技术宅moreD对线性代数中最小下标为1非常不满于是所有下标均从0开始。
输入格式 一个测试点包含多组数据你需要不断读入直到输入结束。 每组数据第一行为一个n接下来第二行输入n个数字是一个0到n-1的排列。
输出格式 输出若干行每行表示对应组数据逆序数奇偶性奇数输出odd偶数输出even。
样例输入
5 0 1 2 3 4 5 4 3 1 2 0
样例输出
even odd
数据规模和约定 设每组测试点T个数据 1T10 1n100000
首先看暴力方法超时仅供理解题意 4 3 1 2 0求逆序数的方法 对于第1个数字4前面没有比它大的数逆序数为0对于3前面有比它大的数字4逆序数为1对于1前面有4,3都比它大逆序数为2对于2 前面有4,3,1两个比它大逆序数为2对于0前面有4,3,1,2都比它大逆序数为4 因此该序列的逆序数012249为odd #includeiostream
using namespace std;int main(){int n;while(cinn){int a[n];for(int i0;in;i){cina[i];}long long int sum0;for(int i1;in;i){for(int j0;ji;j){if(a[j]a[i]) sum;}}if(sum%20) coutevenendl;else coutoddendl;}return 0;
} 归并算法
#includeiostream
using namespace std;
const int N100005;
int a[N];//待排序的数组
int tmp[N];
int res0;void msort(int l,int r){if(lr) return;//只有一个数 int mid(lr)1;msort(l,mid);msort(mid1,r);//合并 int il,jmid1,kl;while(imidjr){if(a[i]a[j]) tmp[k]a[i];else{tmp[k]a[j];resmid-i1;}} while(imid) tmp[k]a[i];while(jr) tmp[k]a[j];for(int il;ir;i) a[i]tmp[i];
}
int main(){int n;while(cinn){res0;for(int i0;in;i){cina[i]; }msort(0,n-1);if(res%20) coutevenendl;else coutoddendl;}return 0;
}
思路归并算法。在右段取数时计算逆序数即取右段中的数时该数的逆序数为左段中比它大的数。
