hihocoder 1399 - shortening sequence

1 描述

There is an integer array A1, A2 …AN. Each round you may choose two adjacent integers. If their sum is an odd number, the two adjacent integers can be deleted.

Can you work out the minimum length of the final array after elaborate deletions?

2 输入

The first line contains one integer N, indicating the length of the initial array.

The second line contains N integers, indicating A1, A2 …AN.

For 30% of the data：1 ≤ N ≤ 10

For 60% of the data：1 ≤ N ≤ 1000

For 100% of the data：1 ≤ N ≤ 1000000, 0 ≤ Ai ≤ 1000000000

3 输出

One line with an integer indicating the minimum length of the final array.

样例提示 (1,2) (3,4) (4,5) are deleted.

样例输入

7
1 1 2 3 4 4 5

样例输出

1

4 实现

经过多轮的筛选删除相邻的奇偶性不同的数，最终剩下的酒只会全是奇数或者全是偶数，所以答案就是奇数和偶数的数目之差的绝对值：

while True:
    try:
        N = raw_input()
        A = [int(ai[-1]) % 2 for ai in raw_input().strip().split()]
        print abs(len(A) - sum(A) * 2)
    except EOFError:
        break

问题是很简单的问题，但是如果用暴力的方法来实现就会超时，限制时间是10秒，如果列表中的数字数目太多，反复的进行del操作就会超时：

while True:
    try:
        N = int(raw_input().strip())
        A = [int(ai[-1]) for ai in raw_input().strip().split()]
        print A
        delete = True
        while delete == True:
            i = 0
            delete = False
            while i < len(A) - 1:
                if ((A[i] + A[i + 1]) % 2) == 1:
                    del A[i], A[i]
                    delete = True
                else:
                    i += 1
        print len(A)
    except EOFError:
        break

所以这道题如果不去思考原理，从原理上来解，暴力算法是无法AC的。