[Nescafé 18&COGS 1045] 七夕祭 题目解析

    注意到本题在洛谷是一道蓝题。所以：论如何在比赛中场切蓝题？（注意，这里没有任何一个人因为没做过交互题而在某比赛中遇到蓝题却受到伤害！！！）

  引入

       你有一个 \(N \times M\) 的矩形网格，其中 \(T\) 个格点是“感兴趣的”。你可以交换相邻的格点（左右相邻或上下相邻，且每行/列的首尾也算相邻，即环形）。目标是用最少的交换次数，同时满足两个条件：

1. 行均等：每一行感兴趣的格点数相同。

2. 列均等：每一列感兴趣的格点数相同。

这是一个典型的环形均分问题。核心思想是：行列独立，可以分别求解。

分析

第 1 步：数据统计与可行性预判

统计行和：设第 \(i\) 行有 \(R_i\) 个感兴趣的格点，则 \(\sum_{i=1}^{N} R_i = T\)。

统计列和：设第 \(j\) 列有 \(C_j\) 个感兴趣的格点，则 \(\sum_{j=1}^{M} C_j = T\)。

 预判可行性：

行方向可行的条件是 \(T\) 能被 \(N\) 整除。此时每行的目标数为 \(\text{avg}_R = \frac{T}{N}\)。

列方向可行的条件是 \(T\) 能被 \(M\) 整除。此时每列的目标数为 \(\text{avg}_C = \frac{T}{M}\)。

第 2 步：将行/列问题转化为一维环形均分问题

以行方向为例，我们得到了一个环形排列的数列 \([R_1, R_2, ..., R_N]\)，需要通过相邻交换（环形），使每个数都变成目标值 \(\text{avg}_R\)。这本质上是一个货物搬运问题。

转化：

我们定义一个“偏差”数组 \(A_i = R_i - \text{avg}_R\)。问题变成了：通过相邻搬运，使所有 \(A_i\) 变为 0。最终答案是所有搬运的“工作量”之和。

第 3 步：求解一维环形均分问题（数学推导）

设从第 \(i\) 个位置搬运到第 \(i+1\) 个位置的货物量为 \(x_i\)（可正可负，正表示向右搬，负表示向左搬）。那么，对于每个位置，经过搬运后，其偏差应该被消除：

\[

   A_i + x_{i-1} - x_i = 0

   \]

其中 \(x_0\) 表示从第 \(N\) 个位置到第 \(1\) 个位置的搬运量（因为是环形）。整理得：

\[

   x_i = A_i + x_{i-1}

   \]

这是一个递推关系。令 \(x_0 = k\)，则可以推出：

\(x_1 = A_1 + k\)

\(x_2 = A_2 + x_1 = A_1 + A_2 + k\)

\(x_3 = A_1 + A_2 + A_3 + k\)

...

 \(x_i = S_i + k\)

其中 \(S_i = \sum_{j=1}^{i} A_j\) 是前 \(i\) 个偏差的前缀和（注意，这里的 \(A_j\) 已经减去平均值，所以整个数列的总和为0，即 \(S_N = 0\)）。

我们的目标是最小化总运输量 \(\sum_{i=1}^{N} |x_i| = \sum_{i=1}^{N} |S_i + k|\)。

问题的几何意义：我们需要找到一个实数 \(k\)，使得数轴上的一系列点 \([-S_1, -S_2, ..., -S_N]\) 到点 \(k\) 的距离之和最小。

数学结论：使距离和最小的点 \(k\) 是这些点坐标的中位数。

第4步：计算最小交换次数

1.  根据第 2 步得到偏差数组 \(A_i\)。

2.  计算其前缀和 \(S_i = A_1 + A_2 + ... + A_i\)，得到一个长度为 \(N\) 的数组 \([S_1, S_2, ..., S_N]\)。

3.  对这个前缀和数组进行排序，找到它的中位数 \(m\)。

4.  最小交换次数即为 \(\sum_{i=1}^{N} |S_i - m|\)。

Ps：这个计算出的次数，实际上是“货物搬运的总量”。因为每次交换（相邻位置）只能搬运“1个单位”的货物，所以这个总量就等于最少的交换次数。

列方向的处理方法与行方向完全相同，只是将 \(N\) 换成 \(M\)，将 \(R_i\) 换成 \(C_j\)。

最终答案

1. 如果两个方向都可行，输出 [code]both[/code] 和行与列次数之和。

2. 如果只有行可行，输出 [code]row[/code] 和行的次数。

3. 如果只有列可行，输出 [code]column[/code] 和列的次数。

4. 如果都不可行，输出 [code]impossible[/code]。

代码如下

#include<bits/stdc++.h>
#define MAXN 100010
#define ll long long
using namespace std;

ll n1,m,t;
ll r[MAXN],c[MAXN],s[MAXN];

ll calc(ll n,ll a[],ll ta)
{
	for(int i=1;i<=n;++i) s[i]=s[i-1]+(a[i]-ta);
	sort(s+1,s+n+1);
	ll mid=s[(n+1)/2];
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=abs(s[i]-mid);
	return ans;
}

int main()
{
	freopen("tanabata.in","r",stdin);
	freopen("tanabata.out","w",stdout);
	cin>>n1>>m>>t;
	memset(r,0,sizeof(r));
	memset(c,0,sizeof(c));
	for(int i=1;i<=t;++i)
	{
		int x,y;
		cin>>x>>y;
		r[x]++; c[y]++;
	}
	bool okr=!(t%n1),okc=!(t%m);
	if(okr&&okc)
	{
		ll rans=calc(n1,r,t/n1);
		ll cans=calc(m,c,t/m);
		cout<<"both "<<rans+cans<<endl;
	}
	else if(okr)
	{
		ll rans=calc(n1,r,t/n1);
		cout<<"row "<<rans<<endl;
	}
	else if(okc)
	{
		ll cans=calc(m,c,t/m);
		cout<<"column "<<cans<<endl;
	}
	else cout<<"impossible"<<endl;
	return 0;
}

更新日志：

2026.3.14 创建题解