T1

题目描述

李华买纪念品的预算为$k$，现给出他心动的纪念品清单：共有$n$件，其中每件都各有其价格$price$，重量$weight$，心动值$v$（其中心动值为1~5之间的数值），需要注意的是：在心动值不同的情况下，李华会优先选择心动值大的纪念品；若心动值相同，李华会优先选择比较便宜的纪念品，具体见样例。同时给出李华在保证不累的情况下，最多能拿的物品重量$m$。在不超过预算并且保证不累的情况下，李华最多可以带几件纪念品回家？

输入描述

第一行三个整数，为纪念品数量$n$，最多能拿的物品重量$m$和预算$k$。
第二行到第$n + 1$行，分别为每件物品的价格$price$，重量$weight$，心动值$v$。

$n < 1e^5$
$m < 100$
$k < 10000$
$price < 10000$
$weight < 100$
$1 < v < 5$

输出描述

在不超过预算并且保证不累的情况下，最多能带回家的纪念品件数。

示例1

样例输入

3 10 1000
100 5 3
50 3 2
300 3 3

样例输出

2

说明

选第一件和第三件

算法

(贪心) $O(nlog(n))$

优先选择心动值大的、价格低的、重量轻的

时间复杂度

瓶颈在物品排序

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, k;

struct Item {
    int p, w, v;

    bool operator< (const Item &item) const {
        if (v != item.v) return v > item.v;
        else if (p != item.p) return p < item.p;
        else return w < item.w;
    }
} items[N];


int main() {
    cin >> n >> m >> k;

    for (int i = 0; i < n; i ++ )
        cin >> items[i].p >> items[i].w >> items[i].v;

    sort(items, items + n);

    int ret = 0, weight = 0, money = 0;

    for (int i = 0; i < n; i ++ ) {
        auto &t = items[i];
        if (weight + t.w <= m && money + t.p <= k) {
            weight += t.w, money += t.p;
            ret ++ ;
        }
    }

    cout << ret;

    return 0;
}

T2

题目描述

一个$N \times N$的棋盘，每个格子填有1、2、3、4中的某一个。最开始在左上角放一个棋子，每次可以移动至上、下、左、右四个格子中的某一个，每次只能移动一格（允许重复移动到某一个格子），在任何时刻都不允许将棋子移除棋盘。在移动时需要进行计分。如果初始格子中的数字为X，目标格子中的数字为Y，则本次移动计分为|X - Y|。现在需要把棋子移动到右下角，求最小计分。

输入描述

第一行为$n$
第二行到第$n + 1$行，为一个二维数组，表示棋盘上的每个格子对应的数字（正整数）。

$1 \leq n \leq 100$

输出描述

最小计分。

示例1

样例输入

3
1 2 4
1 3 1
1 2 1

样例输出

2

算法

(Dijkstra) $O(Mlog(N))$

$N = n ^ 2$个节点，$M = 4 * n * (n - 1)$条有向边

C++ 代码

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

const int N = 110, M = N * N;
typedef pair<int, int> PII;

int n;
int g[N][N];
int h[M], e[M * 4], w[M * 4], ne[M * 4], idx;
int dist[M];
bool st[M];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int bg, ed;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get(int x, int y) {
    return n * (x - 1) + y;
}

void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[bg] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, bg});

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

        int dis = t.x, v = t.second;

        if (st[v]) continue;
        st[v] = true;

        for (int i = h[v]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dis + w[i]) {
                dist[j] = dis + w[i];
                q.push({dist[j], j});
            }
        }
    }
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> g[i][j];

    bg = get(1, 1), ed = get(n, n);

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            for (int k = 0; k < 4; k ++ ) {
                int a = i + dx[k], b = j + dy[k];
                if (a <= 0 || b <= 0 || a > n || b > n) continue;
                add(get(i, j), get(a, b), abs(g[i][j] - g[a][b]));
            }

    dijkstra();

    cout << dist[ed];

    return 0;
}