先弄会前三个题目,七夕祭就搞懂了。

货仓选址

地址货仓选址
题意:给了很多货仓的地址,问家在何处可以使得家到每个货仓的距离和最小,求距离和。
思路:位置排序,取中位数为家,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

Last modification:January 9th, 2021 at 05:47 pm
请赏我杯奶茶,让我快乐长肉