题解：P12842 [蓝桥杯 2025 国 A] 土地整平计划
Sakura_Emilia
·
·
题解
Solution
贪心解法。从前往后扫一遍，记录每一种数出现的位置。再来对每一种数的位置进行从前往后遍历，只要有间隔就有代价，统计最小总代价即可，思路很简单。
最常规的思路就是使用 map<int, queue<int>> 来记录每一种数所出现的各个下标。但是本题卡 map，这种写法只能得 60 分，需要手写数组模拟链表来实现。
模拟链表最简单的一种方案就是直接使用图论板子里面的链式前向星，记录每一种数的各个下标。这里需要注意的是，一般链式前向星的板子是基于头插法加入新节点，对应下标其实是从后往前遍历，这里需要注意。
Code
```cpp
#include <bits/stdc++.h>
#define Ciallo main
#define int long long
using namespace std;
int n, t, key, pre, ans, cost;
map<int, queue<int>> mp;
signed Ciallo(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
for(int i=1; i<=n; i++){
cin >> t;
mp[t].push(i);
}
ans = LONG_LONG_MAX;
for(const auto& tem : mp) {
key = tem.first;
auto q = tem.second;
cost = pre = 0;
while(!q.empty()){
t = q.front();
q.pop();
if(t != pre + 1)
cost += key;
pre = t;
}
if(pre != n)
cost += key;
ans = min(ans, cost);
}
cout << ans << endl;
return 0;
}
```
$100$ 分代码如下：
```cpp
#include <bits/stdc++.h>
#define Ciallo main
#define int long long
using namespace std;
const int N = 2e6 + 8;
inline int read() {
int _x = 0, _w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') _w = -1;
#ifdef __linux__
ch = (char)getchar_unlocked();
#else
ch = (char)_getchar_nolock();
#endif
}
while (ch >= '0' && ch <= '9') {
_x = (_x << 3) + (_x << 1) + (ch - '0');
#ifdef __linux__
ch = (char)getchar_unlocked();
#else
ch = (char)_getchar_nolock();
#endif
}
return _x * _w;
}
inline void write(int _x){
if(_x < 0) {
#ifdef __linux__
putchar_unlocked('-');
#else
_putchar_nolock('-');
#endif
_x = -_x;
}
static int _sta[130];
int _top = 0;
do {
_sta[_top++] = _x % 10, _x /= 10;
} while(_x);
while(_top)
#ifdef __linux__
putchar_unlocked(_sta[--_top] + 48);
putchar_unlocked('\n');
#else
_putchar_nolock(_sta[--_top] + 48);
_putchar_nolock('\n');
#endif
}
int n, t, pre, ans, cost, u;
int has[N], hasIdx;
int h[N], e[N], ne[N], idx;
bool st[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
signed Ciallo() {
n = read();
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i++) {
t = read();
if(!st[t]){
has[++hasIdx] = t;
st[t] = true;
}
add(t, i);
}
ans = LONG_LONG_MAX;
for(int i = 1; i <= hasIdx; i++) {
u = has[i];
if(h[u] == -1)
continue;
cost = 0, pre = n + 1;
for(int j = h[u]; j != -1; j = ne[j]) {
t = e[j];
if(t != pre - 1)
cost += u;
if(cost >= ans)
break;
pre = t;
}
if(pre != 1)
cost += u;
ans = min(ans, cost);
}
write(ans);
return 0;
}
```