#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 160;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int n, m;
char a[N][N];
queue<PII> q;
int res;
int dist[N][N];

int bfs(int sx, int sy)
{
    memset(dist, -1, sizeof dist);
    dist[sx][sy] = 0;
    q.push({sx, sy});

    while (q.size())
    {
        PII t = q.front();
        q.pop();

        for (int i = 0; i < 8; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x <= 0 || x > n || y <= 0 || y > m) continue;
            if (a[x][y] == '*') continue;
            if (dist[x][y] != -1) continue;
            if (a[x][y] == 'H') return dist[t.x][t.y] + 1;

            dist[x][y] = dist[t.x][t.y] + 1;
            q.push({x, y});
        }
    }

    return -1;
}

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i ++ )
        scanf("%s", a[i] + 1);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (a[i][j] == 'K') printf("%d\n", bfs(i, j));

    return 0;
}

一元二次方程一般形式为 $ax^2+bx+c=0$，它的求根公式为：

$$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$$

其中 $\pm$ 表示两个解，$b^2-4ac$ 为判别式，当判别式大于零时方程有两个不相等的实数根，当判别式等于零时方程有一个重根，当判别式小于零时方程无实数根。

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 500010;

LL n, res;
LL a[N], tmp[N];

void merge_sort(LL q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ], res += (LL)mid - i + 1;

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    while (cin >> n && n)
    {
        res = 0;
        for (int i = 0; i < n; i ++ )
            scanf("%lld", &a[i]);

        merge_sort(a, 0, n - 1);

        printf("%lld\n", res);
    }

    return 0;
}

平衡树做法 · $O(n \log n)$

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int p, n, id;

int main()
{
    int x;
    scanf("%d", &p);

    while (p -- )
    {
        multiset<int> S;
        multiset<int>::iterator it;
        vector<int> ans;

        scanf("%d%d", &id, &n);

        for (int i = 1; i <= n; i ++ )
        {
            scanf("%d", &x);
            S.insert(x);

            if (i == 1) it = S.begin();
            else
            {
                if (i & 1)
                {
                    if (x < *it) it -- ;
                }
                else
                {
                    if (x >= *it) it ++ ;
                }
            }
            if (i & 1) ans.push_back(*it);
        }

        printf("%d %d\n", id, (n + 1) / 2);

        bool f = 1;
        for (int i = 0, sz = ans.size(); i < sz; i ++ )
        {
            if (i && i % 10 == 0) puts(""), f = 1;
            if (f) printf("%d ", ans[i]);
            else printf(" %d", ans[i]);
        }
        puts("");
    }

    return 0;
}

对顶堆做法 · $O(n \log n)$

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m, k;
int row[N], col[N];
int s[N], c[N];

LL f(int n, int a[])
{
    for (int i = 1; i <= n; i ++ )
        s[i] = s[i - 1] + a[i];

    if (s[n] % n) return -1;
    int avg = s[n] / n;

    c[1] = 0;
    for (int i = 1; i <= n; i ++ )
        c[i] = s[i - 1] - (i - 1) * avg;

    sort(c + 1, c + n + 1);

    LL res = 0;
    for (int i = 1; i <= n; i ++ )
        res += abs(c[i] - c[(n + 1) / 2]);

    return res;
}

int main()
{
    int x, y;
    scanf("%d%d%d", &n, &m, &k);

    while (k -- )
    {
        scanf("%d%d", &x, &y);
        row[x] ++ , col[y] ++ ;
    }

    LL r = f(n, row), c = f(m, col);
    if (r != -1 && c != -1) printf("both %lld\n", r + c);
    else if (r != -1) printf("row %lld\n", r);
    else if (c != -1) printf("column %lld\n", c);
    else puts("impossible");

    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1010;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int n;
int g[N][N];
queue<PII> q;
PII pre[N][N];

void bfs(int x, int y)
{
    q.push({x, y});
    memset(pre, -1, sizeof pre);
    pre[x][y] = {0, 0};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
            if (g[xx][yy]) continue;
            if (pre[xx][yy].x != -1) continue;

            q.push({xx, yy});
            pre[xx][yy] = t;
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &g[i][j]);

    bfs(n - 1, n - 1);

    PII end(0, 0);
    while (1)
    {
        printf("%d %d\n", end.x, end.y);
        if (end.x == n - 1 && end.y == n - 1) break;
        end = pre[end.x][end.y];
    }

    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1010;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n;
int h[N][N];
queue<PII> q;
bool st[N][N];

void bfs(int x, int y, bool& f1, bool& f2)
{
    q.push({x, y});
    st[x][y] = 1;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 8; i ++ )
        {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
            if (h[xx][yy] != h[t.x][t.y])
            {
                if (h[xx][yy] > h[t.x][t.y]) f1 = 1;
                else f2 = 1;
            }
            else if (!st[xx][yy])
            {
                st[xx][yy] = 1;
                q.push({xx, yy});
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &h[i][j]);

    int r1 = 0, r2 = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (!st[i][j])
            {
                bool f1 = 0, f2 = 0;
                bfs(i, j, f1, f2);
                if (!f1) r1 ++ ;
                if (!f2) r2 ++ ;
            }

    printf("%d %d\n", r1, r2);

    return 0;
}

#include <iostream>

using namespace std;

const int N = 200010;

int n, k, a, b, q;
int d[N];
int t1[N], t2[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int tr[], int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}

int sum(int tr[], int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main()
{
    scanf("%d%d%d%d%d", &n, &k, &a, &b, &q);

    int op, x, y, p;
    while (q -- )
    {
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d%d", &x, &y);
            add(t1, x, min(d[x] + y, b) - min(d[x], b));
            add(t2, x, min(d[x] + y, a) - min(d[x], a));
            d[x] += y;
        }
        else
        {
            scanf("%d", &p);
            printf("%d\n", sum(t1, p - 1) + sum(t2, n) - sum(t2, p + k - 1));
        }
    }

    return 0;
}