https://codeforces.com/contest/1462/problem/E1
題意：給定一個陣列，從這個陣列中挑出三個元素x,y,z,使得max(x,y,z)-min(x,y,z)<=2，問最多能找出多少組，
這題一開始我直接dfs求出所有的組合，然后判斷每一組是否滿足條件，結果例三就超時了…然后自己想了想覺得應該是個求組合數的問題，sort之后從a[1]開始求區間的組合，但是發現有問題，例如1 2 2 3 4，按我的方法就是1-3的組合數求完之后再去加上2-4的組合數，但是1-3之間的2 2 3和2-4之間的2 2 3重合了…然后就想不出了orz
后來去看了下大佬們的題解，知道了避免重復的方法就是sort之后從左到右開始，每次確定a[i]為最小，在a[i]-a[i]+2的范圍內取2個數，例如1 2 2 3中確定1，然后再2 2 3中取兩個數，這樣就能避免重復的情況了…
（注意資料范圍，count要long long ）
#include <bits/stdc++.h>
using namespace std;
#define qc std::ios::sync_with_stdio(0);
const int N = 200001;
int a[N];
int main() {
int t, n;
qc;
cin >> t;
while (t--) {
long long count = 0;
cin >> n;
int r = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
while (a[r + 1] - a[i] <= 2 && r + 1 <= n) {
r++;
}
if (r - i >= 2)
count += (long long)(r - i) * (r - i - 1) / 2;
}
cout << count << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/237099.html
標籤：其他
上一篇：Android ——之流式布局