nyoj-109 數列轉換 (守恆定律)

數列轉換

描述

有一個數列a₁,a₂,a₃...a_n,每次可以從中任意選三個相鄰的數a_i-1 ,a_i , a_{i+1 ,}進行如下操作（此操作稱為“對a_i進行操作”）

(a_i-1,a_i,a_i+1)->(a_i-1+a_i,-a_i,a_i+a_i+1)

給定初始和目標序列，是否能通過以上操作，將初始序列轉換成為目標序列？例如，初始序列(1 6 9 4 2 0)目標序列（7 -6 19 2 -6 6)可經過如下操作：

(1 6 9 4 2 0)->( 1 6 13 -4 6 0)->(1 6 13 2 -6 6)->(7 -6 19 2 -6 6)

請你判斷給定的初始狀態和目標狀態，輸出Yes（能夠轉換）或No（不能轉換）

輸入

第一行是一個正整數N,表示測試數據的組數。(N<=100)
每組測試數據的第一行是一個整數M(3<=M<=1000),表示該組測試數據的起始狀態與結束狀態都有M個數。
每組測試數據的第二行是M個整數Ai(-1000<=Ai<=1000)，表示起始狀態。
每組測試數據的第三行是M個整數Bi(-1000<=Bi<=1000),表示終止狀態。

輸出

如果能夠轉換，輸出Yes
如果不能轉換，輸出No

樣例輸入

2
3
1 2 3
1 3 2
6
1 6 9 4 2 0
7 -6 19 2 -6 6

樣例輸出

No
Yes

思路：

看似很費解的搜索，實際可利用“守恆定律”輕松解決

參考資料：http://www.cnblogs.com/dongsheng/archive/2013/03/04/2943099.html

其精髓在於：只要兩個序列順序求和，經排序後，元素按位對應相等，他們就能通過操作互達。

例如：1， 2， 3 => 1， 3， 2 這組示例，順序求和後轉換為 1， 3， 6 => 1, 4, 6； 升序排序後顯然不能按位對應相等（3 ！= 4），所以他們不能互達；

再如：1，6， 9， 4， 2， 0 => 7, -6, 19, 2, -6, 6 這組, 順序求和後轉換為 1， 7， 16， 20， 22， 22 => 7， 1， 20， 22， 16， 22; 將其升序排序後恰能按位對應相等，所以他們能夠互達。

代碼：

#include 
#include 
#define N 1001

using namespace std;

int a[N] = {0};
int b[N] = {0};

int main()
{
    int loop, n, i;
    cin >> loop;
    while(loop --){
        cin >> n;
        for(i = 0; i < n; i ++){
            cin >> a[i];
            a[i] = a[i] + a[i - 1];
        }
        for(i = 0; i < n; i ++){
            cin >> b[i];
            b[i] = b[i] + b[i - 1];
        }

        sort(a, a + n);
        sort(b, b + n);

	/*	for(i = 0; i < n; i ++){
			if(a[i] != b[i]){
				break;
			}
		}
		if(i != n + 1)
			cout << "NO" << endl;
		else 
			cout << "Yes" << endl;
		*/

        if( equal(a, a + n - 1, b) )		// STL equal() 判斷兩個數組是否相等
			cout << "Yes" << endl;
        else
			cout << "No" << endl;
    }

	return 0;
}