先弄会前三个题目，七夕祭就搞懂了。
货仓选址
地址：货仓选址
题意：给了很多货仓的地址，问家在何处可以使得家到每个货仓的距离和最小，求距离和。
思路：位置排序，取中位数为家，ans += abs(T[i] - T[n / 2]).
均分纸牌问题
地址：均分纸牌问题
题意：给一个数组，其中每个数代表这堆牌的数量，每次只能和相邻的交换这堆的几张牌，问多少次交换可以平分。
思路：设要得到的平均数为ave，再需要两步：
- 先
num[i] = ave - num[i] - 再new T[]用来记录每一堆要移动的牌数,如果num[i] != 0,也就是需要调整（也就是把整个num[i]移到下堆上）
T[i] = num[i] + T[i-1]
代码在此
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int num[n];
long long sum = 0;
for(int i = 0;i < n;i++) {
cin>>num[i];
sum += num[i];
}
int check = sum / n;
for(int i = 0;i < n;i++){
num[i] = check - num[i];
}
int T[n];
int ans = 0;
T[0] = num[0];
for(int i = 1;i < n;i++){
T[i] = T[i-1] + num[i];
}
for(int i = 0;i < n;i++){
if(T[i] != 0 )ans ++ ;
}
cout<<ans;
}
环形均分纸牌问题
题意：和刚刚不同，这次的两端也算相邻，而且移动一张牌算一次操作，求最小操作数。
思路：想法大致一样，但是环就没有开始的地方了。这就是我还没懂的地方结合货舱那道题，认为答案是距离T数组每个数最接近的数，到T数组每个数距离的和，很奇怪。
七夕祭
地址：七夕祭
题意：给一个n * m矩阵，给出有纸牌的位置，判断并计算交换多少次可以让这些纸牌均分。
思路：行列不影响的，因此可以单独看行和列压缩成一维，也就成了上面的环形均分问题。
代码在此
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MaxSize = 100010;
ll T[MaxSize];
ll cal(ll num[],int n){
ll mod = num[0] / n;
for(int i = 1;i <= n;i++) {
num[i] -= mod;
T[i] = T[i-1] + num[i];
}
sort(T+1,T+n+1);
ll ans = 0;
for(int i = 1;i <= n;i++){
ans += abs(T[i] - T[(n+1)/2]);
}
return ans;
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
ll hang[MaxSize] = {0};
ll lie[MaxSize] = {0};
for(int i = 0;i < k;i++){
int x,y;
cin>>x>>y;
hang[x] ++ ;
lie[y] ++ ;
}
for(int i = 1;i <= n;i++) hang[0] += hang[i];
for(int j = 1;j <= m;j++) lie[0] += lie[j];
if(lie[0] % m == 0 && hang[0] % n == 0) printf("both %lld",cal(hang,n) + cal(lie,m));
else if(lie[0] % m == 0) printf("column %lld",cal(lie,m));
else if(hang[0] % n == 0) printf("row %lld",cal(hang,n));
else cout<<"impossible";
}
AcWing真好玩2333
所以说我今天还没有看论文...88
