你认为视频网站如何做推广,服务器机房托管价格,市场营销专业,wordpress书库插件题干#xff1a;
问题描述 n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列#xff0c;但是每次只能交换位置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。开始的时候#xff0c;所有小朋友的不高兴程度都是0。 如果某个小朋友第一次被要求交换…题干
问题描述 n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列但是每次只能交换位置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。开始的时候所有小朋友的不高兴程度都是0。 如果某个小朋友第一次被要求交换则他的不高兴程度增加1如果第二次要求他交换则他的不高兴程度增加2即不高兴程度为3依次类推。当要求某个小朋友第k次交换时他的不高兴程度增加k。 请问要让所有小朋友按从低到高排队他们的不高兴程度之和最小是多少。 如果有两个小朋友身高一样则他们谁站在谁前面是没有关系的。
输入格式 输入的第一行包含一个整数n表示小朋友的个数。 第二行包含 n 个整数 H1 H2 … Hn分别表示每个小朋友的身高。
输出格式 输出一行包含一个整数表示小朋友的不高兴程度和的最小值。
样例输入
3 3 2 1
样例输出
9
样例说明 首先交换身高为3和2的小朋友再交换身高为3和1的小朋友再交换身高为2和1的小朋友每个小朋友的不高兴程度都是3总和为9。
数据规模和约定 对于10%的数据 1n10 对于30%的数据 1n1000 对于50%的数据 1n10000 对于100%的数据1n1000000Hi1000000。
解题报告
我就说嘛、、、过了70%不可能是思路错误检查了半天发现最后的统计答案爆了longlong、、、气死我了。
这题的关键在于看到交换的条件是只能交换相邻的两个元素。这就使得问题简单了很多。考虑到x这个数假设最后肯定要被交换到对应的位置上那么看最少需要被交换多少次在看这个次数能否可以实现。不难发现最少被交换的次数就是和前面比他大的数字并且和后面比他小的数字。所以求该数对应的逆序数就行了。那么这个次数能否实现呢不妨这样想只考虑第i个数假设前面比他大的有x1个后面比他小的有x2个我们先想办法将他前面比他大的数都交换到他后面去这样他移动的次数就肯定是x1并且得到的这样一个状态肯定是在他本该在的位置的前面然后我们再通过和后面的数字的交换让他回到原来的位置就可以了这一套操作是x2次所以总次数可以达到x1x2次。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e6 5;
int a[MAX];
int c[MAX];
int lowbit(int x){return x(-x);}
int query(int x) {int res 0;while(x0) {res c[x];x-lowbit(x);}return res;
}
void update(int x,int val) {while(xMAX) {c[x] val;xlowbit(x);}
}
int ans1[MAX],ans2[MAX],ans[MAX];
int main()
{int n;cinn;for(int i 1; in; i) {scanf(%d,ai);a[i];}for(int i n; i1; i--) {ans1[i] query(a[i]-1);update(a[i],1);}memset(c,0,sizeof c);for(int i 1; in; i) {ans2[i] query(1000010) - query(a[i]);update(a[i],1);}for(int i 1; in; i) ans[i] ans1[i] ans2[i];ll res 0;for(int i 1; in; i) {res 1LL*(1ans[i])*ans[i]/2;}printf(%lld\n,res);return 0 ;
}
