首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7524

求逆序对问题(2024-3-5级) 给定N个数的序列a 1 ,a 2 ,...a N ,定义一个数对(a i , a j )为“重要逆序对”的充要条件为 i <…

求逆序对问题(2024-3-5级)

给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。

时间限制:1000

内存限制:256000

输入

本题有多个测试点,每个测试点分为两行:第一行为序列中数字的个数N(1 ≤ N ≤ 200000),第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000),由空格分开。N=0表示输入结束。

输出

每个测试点一行,输出一个整数,为给序列中“重要逆序对”的个数。


样例输入

10

0 9 8 7 6 5 4 3 2 1

0

样例输出

16

提示

请注意答案范围,如果使用printf输出long long类型,请用%lld

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;iostream&gt; using namespace std; int arr[200005]; int tmp[200005]; int N; long long mergesort(int start, int end) {   long long cnt = 0, mid = (start + end) / 2;   if (start &gt;= end)     return 0;   cnt += mergesort(start, mid);   cnt += mergesort(mid + 1, end);   // find important reverse pair   int i = start, j = mid + 1;   while (i &lt;= mid &amp;&amp; j &lt;= end) {     if (arr[i] &gt; 2 * arr[j] &amp;&amp; j &lt;= end) {       cnt += (mid - i + 1);       j++;     } else {       i++;     }   }   // merge sort   i = start, j = mid + 1;   int idx = 0;   while (i &lt;= mid &amp;&amp; j &lt;= end) {     if (arr[i] &gt; arr[j]) {       tmp[idx++] = arr[j++];     } else {       tmp[idx++] = arr[i++];     }   }   while (i &lt;= mid)     tmp[idx++] = arr[i++];   while (j &lt;= end)     tmp[idx++] = arr[j++];   for (int k = 0; k &lt; idx; k++) {     arr[start + k] = tmp[k];   }   return cnt; } int main() {   while (cin &gt;&gt; N) {     if (N == 0)       break;     for (int i = 1; i &lt;= N; i++) {       cin &gt;&gt; arr[i];     }     cout &lt;&lt; mergesort(1, N) &lt;&lt; endl;   }   return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; using namespace std;   int arr[200005]; int tmp[200005]; int N;   long long mergesort(int start,int end){     long long cnt=0, mid=(start+end)/2;     if(start&gt;=end) return 0;     cnt+=mergesort(start,mid);     cnt+=mergesort(mid+1,end);     int i=start,j=mid+1;     while(i&lt;=mid &amp;&amp; j&lt;=end){         if(arr[i]&gt;2*arr[j] &amp;&amp; j&lt;=end){             cnt+=(mid-i+1);             j++;         }else{             i++;         }     }     i=start,j=mid+1;     int idx=0;     while(i&lt;=mid &amp;&amp; j&lt;=end){         if(arr[i]&gt;arr[j]){             tmp[idx++]=arr[j++];         }else{             tmp[idx++]=arr[i++];         }     }     while(i&lt;=mid) tmp[idx++]=arr[i++];     while(j&lt;=end) tmp[idx++]=arr[j++];     for(int k=0;k&lt;idx;k++){         arr[start+k]=tmp[k];     }     return cnt; }   int main(){     while(cin&gt;&gt;N){         if(N==0) break;         for(int i=1;i&lt;=N;i++){             cin&gt;&gt;arr[i];         }         cout&lt;&lt;mergesort(1,N)&lt;&lt;endl;     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。