網易2018校園招聘程式設計真題之重排數列

題目

小易有一個長度為N的正整數數列A = {A[1], A[2], A[3]…, A[N]}。

牛博士給小易出了一個難題:

對數列A進行重新排列,使數列A滿足所有的A[i] * A[i + 1](1 ≤ i ≤ N - 1)都是4的倍數。

小易現在需要判斷一個數列是否可以重排之後滿足牛博士的要求。

輸入描述:

輸入的第一行為數列的個數t(1 ≤ t ≤ 10),

接下來每兩行描述一個數列A,第一行為數列長度n(1 ≤ n ≤ 10^5)

第二行為n個正整數A[i](1 ≤ A[i] ≤ 10^9)

輸出描述:

對于每個數列輸出一行表示是否可以滿足牛博士要求,如果可以輸出Yes,否則輸出No。

輸入例子1:

2

3

1 10 100

4

1 2 3 4

輸出例子1:

Yes

No

解題思路

本題要求連續的兩個數相乘為4的倍數，一看題目就覺得可能要動手把符合要求的數組找到，存在找到一個就行。  
如果不存在，那就要判斷所有數組序列都不滿足要求了，其實這樣想就陷入絕境了。因為判斷不符合的代價太大。  
我們來逆向思維，看看符合條件的序列是什麼樣子的。

相鄰的兩個數相乘為4的倍數，隻有三種情況，兩個數都是4的倍數，隻有一個是4的倍數，兩個數都是2的倍數但都  
不是4的倍數。我們首先看至少有多少個4的倍數的元素，該數組一定符合條件。有n個元素，相鄰相乘，則可以隔一  
位放一個4的倍數的元素，則需要n/2(向下取整，考慮n位奇數情況)個4的倍數的元素。如果數組中存在大于等于  
n/2個4的倍數的元素，那麼我們可以肯定一定能符合條件了。

如果數組元素中4的倍數少于n/2個，也不要緊，隻要還存在2的倍數（不是4的倍數）的數即可。那麼又要多少個這  
樣的數呢？假設存在k個4的倍數的元素（k<n/2，向下取整）,那麼這k個數可以搭配2k個數讓其符合要求（為啥不  
是2k+1呢？好好想想，序列有一端是不是還要連接配接剩下的元素？），如此還剩下n-2k個數。現已經沒有4的倍數的  
元素可以搭配了，那麼剩下的元素必須都是2的倍數，兩兩相乘才是4的倍數。這樣才符合要求。這麼一來，在當4的  
倍數的元素小于n/2的情況下，數組中至少存在n-2k個元素是2的倍數但不是4的倍數，這樣也符合條件。

找出符合要求的條件後那麼我們隻需統計數組元素中4的倍數有多少個，2的倍數但不是4的倍數有多少個，看看符不  
符合要求即可。
           

代碼

#include<iostream>
using namespace std;
int main()
{
    int n;
    while (cin >> n)
    {
        for (int i = ; i < n; i++)
        {
            int ln;
            cin >> ln;
            int num4 = ;
            int num2n4 = ;
            for (int j = ; j < ln; j++)
            {
                int d;
                cin >> d;
                if (d %  == )
                {
                    num4++;
                }
                else if (d %  == )
                {
                    num2n4++;
                }
            }
            if (num4 >= ln / )
            {
                cout << "Yes" << endl;
            }
            else if (num2n4 >= (ln -  * num4))
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
    }
    system("pause");
}
           

程式送出，運作通過。