HDU 5806 NanoApe Loves Sequence Ⅱ

垃圾题！！！！！！

首先我在此表示，我怀疑整个网上的题解和题目都是错的！！！！！！！

我的个人理解包括所有网上的题解都说的是这样的题意：

满足区间中第k大的数必须大于等于 m 的数量。

恩，感觉不是很好想，觉得终于碰到了难一点的题目了。脑子拙劣的我还想到快排求序列第k大去了……

后来看了题解，很多题解，题意跟我想的是一个意思。但他们的题解都是这么说的。只要一个序列，大于等于m的数量大于等于k，那么这个数列必定符合要求……………………

mather fucker ？？？？

那我小于m的数字无穷多怎么办？？？？

附上我个人认为正确理解的正确代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

int main()
{
    int n, m, k, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &k);
        each(i, n) scanf("%d", ary + i), ary[i] = ary[i] < m ? 1 : 0;
        int i = 0, j = 0, sum = 0;
        ll ans = 0;
        while (i < n) {
            while (sum < k && j < n)
                sum += ary[j++];
            if (sum == k)
                sum -= ary[--j];
            if (sum == k && j - i < k)
                break;
            ans += (j - i - 1);
            sum -= ary[i++];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

再附上网上的思路代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

int main()
{
    int n, m, k, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &k);
        each(i, n) scanf("%d", ary + i), ary[i] = ary[i] < m ? 0 : 1;
        int l = 0, r = 0, sum = 0;
        ll ans = 0;
        while (l < n) {
            while (sum < k && r < n)
                sum += ary[r++];
            if (sum < k)
                break;
            ans += (n - r + 1);
            sum -= ary[l++];
        }
        printf("%lld\n", ans);
    }
    return 0;
}