思路:
必要性:一个骨牌必由黑和白组成 充分性:考虑选择一对黑格和白格,然后选择一条它们之间的路径,这条路径满足除起点和终点之外都是已匹配的格子,那么对这条路径进行调整就可以得到满足条件的解。
代码:
#include<bits/stdc++.h> using namespace std; #define int long long int n; const int N = 3e5 + 10; signed main(){ cin >> n; int black = 0,white = 0; for(int i=1;i<=n;i++){ int x; cin >> x; black += x / 2; white += x / 2; if(x & 1){ if(i & 1) black++; else white++; } } cout << min(black,white) << endl; return 0; }