P6170题解
Kreado
·
·
题解
题目传送门
一道很好的数论题。
题意：
有 n 头奶牛，分布在一些房间，某些房间可能有多头牛，要让这些牛按顺时针移动，使每一个房间恰好有一个奶牛的最小花费。
花费计算：如果一头奶牛穿过了 d 扇门，他消耗的能量为 d^2 。
思路:
对于这道题，我可以直说，用暴力就行了，根本不需要其他的技巧。
首先说一个东西：如果有 1 头奶牛在 a 点，1 头奶牛在 b 点，还有一个没有奶牛的 c 点，且 c>b>a，要想有一头奶牛在 b 点，一头奶牛在 c 点，方案 a \to b,b \to c 比方案 a \to c 好。
因为 \sum c_i = n，且要使得 \forall c_i = 1，每头奶牛走的步数最少，所以可以直接从第 1 个房间开始遍历，如果 c_i > 1 ，就把这个房间的 (c_i-1) 头奶牛移到后面的一个房间，留在这个房间里的奶牛一定是步数走的最多的，所以不用判断每头奶牛的新旧，以此类推，直到满足 \forall c_i =1，循环结束。
比如说:
样例数据 : 10 1 0 0 2 0 0 1 2 2 2.
明显最优的方案是：
如果一个一个走的话，时间复杂度是 $O(n^2)$，不会爆。
但是如果全部走的话，时间复杂度是 $O(n)$，刚好。
## 贴贴代码
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node{ll N,S,W;}a[101000];
// N 当前房间的下一个房间
// S 当前房间还有多少头牛
// W 当前房间还有多少头牛
ll n,ans,p=1;
int main(){
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i].S;
for(ll i=1;i<=n;i++)
a[i].N=i+1;
a[n].N=1;
// 记录当前房间的下一个房间的编号
for(ll i=1;i<=2*n;i++){
if(a[p].S>1){
a[a[p].N].S+=a[p].S-1;
a[a[p].N].W+=a[p].S-1;
a[p].S=1;
}
p=a[p].N;
}
for(ll i=1;i<=n;i++) ans+=(a[i].W*a[i].W);
printf("%lld",ans);
return 0;
}
```
时间复杂度还挺低 , $O(n)$。
~~这样你就能一下 A 两道题啦~~