題目鏈接：點擊查看

題目大意：給出一個長度為 n 的序列，可以選擇某些位置使得 a[ i ] =? - a[ i ]，問逆序對最少可以是多少

題目分析：需要看出的一個關系就是，在某一對關系 ( i?, j?) 中，a[ i?] 和 a[ j ] 絕對值較大的數字會起到決定性的作用，分類枚舉一下就是：假設 i < j 且 abs( a[ i ] ) > abs( a[ j ] )

a[ i ] >?a[ j ]，貢獻為 1

a[ i ] > -a[ j ]，貢獻為 1

-a[ i ] < a[ j ]，貢獻為 0

-a[ i ] < -a[ j ]，貢獻為 0

所以對于每個位置 i 來說，只需要統計一下前后各有多少個絕對值比自己小的數字分別記為 cnt1 和 cnt2 即可，意思就是，如果 a[ i ] 為正數的話，會提供 cnt2 的貢獻，為負數的話會提供 cnt1 的貢獻，所以貪心去選擇就好了

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int a[N];int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",a+i);a[i]=abs(a[i]);}int ans=0;for(int i=1;i<=n;i++){int cnt1=0,cnt2=0;for(int j=1;j<i;j++)cnt1+=a[j]<a[i];for(int j=i+1;j<=n;j++)cnt2+=a[j]<a[i];ans+=min(cnt1,cnt2);}printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 351E Jeff and Permutation(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。