希望对大家有点帮助

原题链接：1295.[COCI-2006_2007-contest3]#5 TENKICI

༺ཌ༒༺ཌༀཉAC༃ༀད༻༒ད༻

2025-11-06 20:08:51

发布于：福建

0阅读

0回复

0点赞

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

struct Tank {
int id, r, c, tr, tc; // 目标行、目标列
};

int main() {
int N;
cin >> N;
vector<Tank> tanks(N);
for (int i = 0; i < N; i++) {
cin >> tanks[i].r >> tanks[i].c;
tanks[i].id = i + 1;
}

// 行匹配：按初始行排序，匹配到 1..N
vector<int> rows(N);
for (int i = 0; i < N; i++) rows[i] = tanks[i].r;
sort(rows.begin(), rows.end());
vector<int> target_rows(N);
for (int i = 0; i < N; i++) target_rows[i] = i + 1;

// 列匹配：按初始列排序，匹配到 1..N
vector<int> cols(N);
for (int i = 0; i < N; i++) cols[i] = tanks[i].c;
sort(cols.begin(), cols.end());
vector<int> target_cols(N);
for (int i = 0; i < N; i++) target_cols[i] = i + 1;

// 分配目标行、目标列
// 这里需要将排序后的目标映射回原坦克
// 更简单的方法：直接对坦克按行排序，分配目标行 1..N，然后恢复原顺序
vector<Tank> tmp = tanks;
sort(tmp.begin(), tmp.end(), [](const Tank& a, const Tank& b) {
    return a.r < b.r;
});
for (int i = 0; i < N; i++) {
    tmp[i].tr = i + 1;
}
// 恢复原顺序
sort(tmp.begin(), tmp.end(), [](const Tank& a, const Tank& b) {
    return a.id < b.id;
});
// 列同理
sort(tanks.begin(), tanks.end(), [](const Tank& a, const Tank& b) {
    return a.c < b.c;
});
for (int i = 0; i < N; i++) {
    tanks[i].tc = i + 1;
}
// 恢复原顺序
sort(tanks.begin(), tanks.end(), [](const Tank& a, const Tank& b) {
    return a.id < b.id;
});
// 合并行列目标
for (int i = 0; i < N; i++) {
    tanks[i].tr = tmp[i].tr;
}

// 计算总步数
int total_steps = 0;
for (int i = 0; i < N; i++) {
    total_steps += abs(tanks[i].r - tanks[i].tr) + abs(tanks[i].c - tanks[i].tc);
}

// 输出总步数
cout << total_steps << endl;

// 生成移动序列：先行后列，避免碰撞
// 先行：先移动行差最大的？其实可以一行一行处理
// 简单方法：多次扫描，每次移动一步
vector<string> moves;

// 调整行
bool changed = true;
while (changed) {
    changed = false;
    for (int i = 0; i < N; i++) {
        if (tanks[i].r < tanks[i].tr) {
            // 向下
            moves.push_back(to_string(tanks[i].id) + " D");
            tanks[i].r++;
            changed = true;
        }
    }
    for (int i = 0; i < N; i++) {
        if (tanks[i].r > tanks[i].tr) {
            // 向上
            moves.push_back(to_string(tanks[i].id) + " U");
            tanks[i].r--;
            changed = true;
        }
    }
}

// 调整列
changed = true;
while (changed) {
    changed = false;
    for (int i = 0; i < N; i++) {
        if (tanks[i].c < tanks[i].tc) {
            // 向右
            moves.push_back(to_string(tanks[i].id) + " R");
            tanks[i].c++;
            changed = true;
        }
    }
    for (int i = 0; i < N; i++) {
        if (tanks[i].c > tanks[i].tc) {
            // 向左
            moves.push_back(to_string(tanks[i].id) + " L");
            tanks[i].c--;
            changed = true;
        }
    }
}

// 输出移动
for (const string& m : moves) {
    cout << m << endl;
}

return 0;

}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论