习题:七夕祭(杂题)

题目

习题:七夕祭(杂题)

思路

首先一点如果是impossible,那么一定

\(T\%N\)和\(T\%M\)都不为0

再接着,

因为竖着满足跟横着满足本质上是一样的,所以这里只讨论横着满足

并且如果要满足横着的情况,

如果要步数最小,那么我们一定不会将竖着的摊位交换

同理,如果要满足竖着的情况,我们一定不会将横着的摊位交换

也就是说如果我们定义两个数组row和col来维护每一行和每一列的摊位个数

那么竖着交换对col数组没有任何影响,横着交换对row数组也没有任何影响

也就是指,如果是both的话,

我们只需要将横着交换的最小值和竖着交换的最小值相加即可

因为我们只需要横着满足,所以我们其实并不在意整个矩阵长成什么样子

我们所需要知道的,只是每一横着有多少个摊点

问题转换为:

现在我们有一个环,我们只能使相邻的元素一个+1,一个-1,求最小的步数使这个数列的元素变为一样

然后?

这个模型你们不熟悉?

如果真不熟悉的话,

蒟蒻笔者还是解释一下

t就是题意中的t

我们先对于每一个元素求出他到指定元素的差距,即\(row_i=row_i-t/n\)

接着求出前缀和数组\(srow\),然后求出对\(srow\)排序之后的中点\(mid=srow_{(n+1)/2}\),n+1是防止精度

最后\(ans=\sum_{i=1}^{n}abs(srow_i-mid)\)

那么问题来了,原理是什么?

考虑一下,\(srow_i\)表示什么?

其实就是1~i之中总共需要对外部所提供的贡献,或者他需要外界所需的贡献

我们定义对外部的贡献为正,所需的贡献为负

现在讨论的\(srow\)是指没有排序的\(srow\)

我们先指定一个点k

\(srow_k-srow_1\)的意义是什么?

不就是2~k这个区间为了使1到达平均元素时候的贡献

那么\(srow_k-srow_2\)的意义是什么?

同理,就是3~k这个区间为了使1~2这个区间的和达到平均时所作的贡献

那么\(srow_k-srow_1+srow_k-srow_2\),意义是什么?

不就是先使1达到平均,再使1~2这个区间的和达到平均的贡献和

因为1我们已经付出代价将其达到平均,所以2也一定是平均的,

所以对于一个指定的k

\(ans=\sum_{i=1}^{n}abs(srow_i-srow_k)\)

很明显,当k为中位数的时候最小

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
struct node
{
    int x,y;
}a[200005];
int n,m,t;
int col[200005];
int row[200005];
int s_row[200005];
int s_col[200005];
int ans_row;
int ans_col;
int f_abs(int x)
{
    if(x<0)
        return -x;
    return x;
}
signed main()
{
    cin>>n>>m>>t;
    if(t%n!=0&&t%m!=0)
    {
        cout<<"impossible";
        return 0;
    }
    for(int i=1;i<=t;i++)
    {
        cin>>a[i].x>>a[i].y;
        row[a[i].x]++;
        col[a[i].y]++;
    }
    if(t%n==0)
    {
        for(int i=1;i<=n;i++)
            row[i]=row[i]-t/n;
        for(int i=1;i<=n;i++)
            s_row[i]=s_row[i-1]+row[i];
        sort(s_row+1,s_row+1+n);
        int mid=s_row[n/2];
        for(int i=1;i<=n;i++)
            ans_row+=f_abs(mid-s_row[i]);
    }
    if(t%m==0)
    {
        for(int i=1;i<=m;i++)
            col[i]=col[i]-t/m;
        for(int i=1;i<=m;i++)
            s_col[i]=s_col[i-1]+col[i];
        sort(s_col+1,s_col+1+m);
        int mid=s_col[m/2];
        for(int i=1;i<=m;i++)
            ans_col+=f_abs(mid-s_col[i]);
    }
    if(t%n==0&&t%m==0)
    {
        cout<<"both "<<ans_row+ans_col;
        return 0;
    }
    if(t%n==0)
    {
        cout<<"row "<<ans_row;
        return 0;
    }
    if(t%m==0)
    {
        cout<<"column "<<ans_col;
        return 0;
    }
    return 0;
}
上一篇:hdu-3038 (带权并查集)


下一篇:【雕爷学编程】MicroPython动手做(01)——春节后入手了K210开发板