34B. Sale

greedy, sorting, 900, https://codeforces.com/problemset/problem/34/B

# #include <iostream>
#include <queue>
using namespace std;

int main(){
    int a,b,h;
    h=0;
    cin>>a>>b;
    priority_queue<int> pq;
    while(a--){
        int x;
        cin>>x;
        if(x>=0) continue;
        pq.push(-x);
        h-=x;
    }
    int ans=0;
    if(b>pq.size()) cout<<h<<'\n';
    else{
        for(int i=0;i<b;i++){
            ans+=pq.top();
            pq.pop();
        }
        cout<<ans<<'\n';
    }
    return 0;
}

思路：按字典序选择起点与扩展顺序，保证得到的是全局字典序最小的完整骑士巡游路径；

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

struct Pos { int r, c; }; 

string label(int r, int c) { // 转成例如 "A1"
    string s;
    s.push_back(char('A' + c));
    s += to_string(r + 1);
    return s;
}

int dr[8] = { 2, 2, 1, 1,-1,-1,-2,-2};
int dc[8] = { 1,-1, 2,-2, 2,-2, 1,-1};

bool dfs(int p, int q, Pos u, int step, vector<vector<int>>& vis, vector<Pos>& path) {
    if (step == p * q) return true;


    vector<Pos> cand;
    for (int k = 0; k < 8; ++k) {
        int nr = u.r + dr[k], nc = u.c + dc[k];
        if (nr >= 0 && nr < p && nc >= 0 && nc < q && !vis[nr][nc]) {
            cand.push_back({nr, nc});
        }
    }
    sort(cand.begin(), cand.end(), [&](const Pos& a, const Pos& b){
        // 先按列字母，再按行数字
        if (a.c != b.c) return a.c < b.c;
        return a.r < b.r;
    });

    for (auto v : cand) {
        vis[v.r][v.c] = 1;
        path.push_back(v);
        if (dfs(p, q, v, step + 1, vis, path)) return true;
        path.pop_back();
        vis[v.r][v.c] = 0;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    if (!(cin >> n)) return 0;
    for (int tc = 1; tc <= n; ++tc) {
        int p, q; // p 行(数字 1..p), q 列(字母 A..)
        cin >> p >> q;

        cout << "Scenario #" << tc << ":\n";

        bool found = false;
       
        for (int c0 = 0; c0 < q && !found; ++c0) {
            for (int r0 = 0; r0 < p && !found; ++r0) {
                vector<vector<int>> vis(p, vector<int>(q, 0));
                vector<Pos> path;
                vis[r0][c0] = 1;
                path.push_back({r0, c0});
                if (dfs(p, q, {r0, c0}, 1, vis, path)) {
                    // 输出路径（拼接标签）
                    string out;
                    for (auto &pt : path) out += label(pt.r, pt.c);
                    cout << out << "\n\n";
                    found = true;
                }
            }
        }
        if (!found) {
            cout << "impossible\n\n";
        }
    }
    return 0;
}