题目描述： 小 A 现在有一个长度为 𝑛 的序列 {𝑥𝑖}，但是小 A 认为这个序列不够优美。 小 A 认为一个序列是优美的，当且仅当存在 𝑘 ∈ [1, 𝑛]，满足： 𝑥1 ≤ 𝑥2 ≤ … ≤ 𝑥𝑘 ≥ 𝑥𝑘+1 ≥ … ≥ 𝑥𝑛 现在小 A 可以进行若干次操作，每次可以交换序列中相邻的两个项，现在他想知道最少操作多少次之后能够使序列变为优美的。
输入： 第一行一个正整数 𝑛，表示序列的长度。 接下来一行 𝑛 个整数，表示初始的序列。
输出： 输出一行一个整数，表示最少需要的操作次数。
这道题看起来比较简单，但是怎么看都感觉不对。 一开始的想法是找一个点分两段分别让它们满足题目要求。 后来发现这有问题，而且自己不会（我太弱了
对于这个方法的Hack数据： 20 3 4 10 9 8 8 7 1 6 5 5 5 5 5 5 5 5 5 5 5
答案是7。貌似错误方法会输出12。
然后突然猛然发现：我们可以对于每一个点，考虑它移向左边或者移向右边。 这样不就好了吗？点之间由于大小是没有影响的，反正改排你前面的就排你前面，排后面的就排后面。
可是突然感觉这样子做好像出现重复的数就会挂。手玩了几个数据发现没什么问题，就交了。但是感觉还是不妥。
估了60pts，实际上有100。
#include <cstdio> #include <cstring> using namespace std; const int N = 100010; inline int min(int a,int b) { return a < b ? a : b; } inline void read(int &x) { char ch = getchar(); x = 0; for(;ch < '0' || ch > '9';) ch = getchar(); for(;ch >= '0' && ch <= '9';) x = x * 10 + (ch ^ '0'), ch = getchar(); } int t[N << 2],ans; int n,a[N],f[N],g[N]; #define ls p << 1 #define rs ls | 1 void insert(int p,int x,int tl,int tr) { if(tl > tr) return; if(tl == tr) { t[p] += 1; return; } int mid = tl + tr >> 1; x <= mid ? insert(ls,x,tl,mid) : insert(rs,x,mid + 1,tr); t[p] = t[ls] + t[rs]; } int query(int p,int l,int r,int tl,int tr) { if(tl > tr) return 0; if(l <= tl && tr <= r) return t[p]; int mid = tl + tr >> 1,ret = 0; if(mid >= l) ret += query(ls,l,r,tl,mid); if(mid < r) ret += query(rs,l,r,mid + 1,tr); return ret; } int main() { freopen("time.in","r",stdin); freopen("time.out","w",stdout); read(n); for(int i = 1;i <= n; ++ i) read(a[i]), f[i] = query(1,a[i] + 1,N,0,N), insert(1,a[i],0,N); memset(t,0,sizeof t); for(int i = n;i; -- i) { int tmp = query(1,a[i] + 1,N,0,N); ans += min(f[i],tmp), insert(1,a[i],0,N); } printf("%d",ans); fclose(stdin); fclose(stdout); return 0; }我考场写了线段树。树状数组的实现更加优秀。 毕竟不用维护什么嘛。。。
