当前位置: 首页 > 工具软件 > Places > 使用案例 >

Take Your Places!(思维)

子车青青
2023-12-01

题目

Take Your Places!


问题描述

给定序列长度n以及序列 { a 1 , a 2 . . . . . . a n } \{a_1,a_2......a_n\} {a1,a2......an}
每次操作允许移动相邻的两个位置,比如 a i a_i ai a i + 1 a_{i+1} ai+1,
问至少经过多少次操作可以使得序列中的数按奇偶参差排列。


分析

在输入数据的过程中,可以对数据进行一次统计,统计其中包含奇数与偶数的个数,以odd表示奇数个数,以even表示偶数个数。
由于满足参差排布,所以 a b s ( o d d − e v e n ) ≤ 1 abs(odd-even)\leq1 abs(oddeven)1,当两数之差大于1时,便无法组成参差排布,也就输出-1;

再分析题目要求,题目要求操作次数最小,也就是使用贪心的策略,结论就是结合奇偶个数情况,再根据每个值的奇偶情况以及其在奇数序列(或偶数序列)中的位序,就可以得知其最终的位置。

以序列 [ 6 , 2 , 3 , 4 , 5 , 1 ] [6,2,3,4,5,1] [6,2,3,4,5,1]为例,奇数有3个,偶数有3个,所以此时有两种排布策略,但不知道哪种是最优的,不妨先以偶数作为第一个。
偶数序列为 [ 6 , 2 , 4 ] [6,2,4] [624],若6为第一个,那么2就为第三个,4就为第五个,再结合其最终位置和当前位置,就可以得到完成偶数序列的最小操作次数,当偶数排好后,当然奇数也就排好了。

再处理以奇数作为第一个的情况,同样可以得到最小操作次数,输出二者最小值即可。

当奇偶个数不同时,那么就直接确定了谁作为第一个,也就更加方便了。

其实我们发现关于次数的计算都可以在输入数据时同步计算,所以不妨在输入时直接都求出来,最后根据 o d d odd odd e v e n even even的情况再进行选择。

代码

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
int t,n;
int a[100005];
int main(){
   cin>>t;
   while(t--){
   		int o=0,j=0;
   		ll ans1=0,ans2=0;
   		ll cnt=0,tnk=0;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
			if(a[i]%2==0){
				o++;
				ans1+=abs(i-cnt*2);
				cnt++;
			}
			else {
				j++;
				ans2+=abs(i-tnk*2);
				tnk++;
			}
		}
		if(abs(o-j)>1){
			cout<<-1<<endl;
		}
		else if(o==j){
			cout<<min(ans1,ans2)<<endl;
		}
		else if(o-j==1){
			cout<<ans1<<endl;
		}
		else{
			cout<<ans2<<endl;
		}
   }
    return 0;
}
 类似资料: