HDU 6188 Duizi and Shunzi

棧。

將數字排序后，一個一個壓入棧。如果棧頂兩個元素形成了對子，那么$ans+1$，彈出棧頂兩個元素；如果棧頂三個元素形成了順子，那么$ans+1$，彈出棧頂三個元素。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1000000 + 10;
int n;
int a[maxn];
int b[maxn];
int c[maxn];int main() {while(~scanf("%d", &n)) {memset(a, 0, sizeof a);for(int i = 1; i <= n; i ++) {int x;scanf("%d", &x);a[x] ++;}int ans = 0;int num = 0;int top = -1;for(int i = 1; i <= n; i ++) {while(a[i] --) {c[++ num] = i;}}for(int i = 1; i <= n; i ++) {if(top == -1) {top ++;b[top] = c[i];} else {if(c[i] == b[top]) {top --;ans ++;} else {if(top < 1) {top ++;b[top] = c[i];} else {if(b[top - 1] + 1 == b[top] && b[top] + 1 == c[i]) {top --;top --;ans ++;} else {top ++;b[top] = c[i];}}}}}printf("%d\n", ans);}return 0;
}