题目1 : Shortening Sequence
- 时间限制:10000ms
- 单点时限:1000ms
- 内存限制:256MB
描述
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?
输入
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
输出
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
参考答案1：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fst first
#define snd second
const int MAXN = 100010;
int main(void) {
int n;
cin >> n;
vector<int> st;
for (int i = 0; i < n; ++ i) {
int x;
cin >> x;
if (!st.empty() && (st.back() + x) % 2 == 1) st.pop_back();
else st.push_back(x);
}
cout << st.size() << endl;
return 0;
}
参考答案2：
#include <iostream>
using namespace std;
int main()
{
int N, ans = 0, data;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> data;
if (data & 1) ans++;
else ans--;
}
if (ans >= 0) cout << ans << endl;
else cout << -ans << endl;
return 0;
}
