首页 技术 正文
技术 2022年11月23日
0 收藏 673 点赞 2,497 浏览 1308 个字

【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=3032

【算法】

交换左右两个相邻格子的摊点,不会改变这一行的摊点个数

交换上下两个相邻格子的摊点,不会改变这一列的摊点个数

因此,题目中所要求的两个问题是独立的,可以分别计算,以第一问 : 每列摊点个数相等,进行讨论 :

我们将每列中的初始摊点个数记为Ai,如果感兴趣的摊点总数不能被M整除,则无解,否则,等价于一个“环形均分纸牌”的问题,

如果不允许“环形传递”,那么最少移动步数为 sigma( | Si | ),Si为Ai – T / M的前缀和

如果允许,仔细思考后会发现,一定有一种最优解的方案,使得环上两个人不进行传递,考虑将环断开 :

假设断开位置为k,那么断开后,每个人的纸牌个数和前缀和分别为 :

Ak+1 Sk+1 – Sk

Ak+2 Sk+2 – Sk

Am Sm – Sk

A1 S1 + Sm – Sk

Ak Sk + Sm – Sk

因为Sm = 0,所以,前缀和数组与一般情况的差别就是每个位置都减了Sk

所以若断开位置为k,最少交换次数为 : sigma( | Si – Sk| ) , 当Sk取前缀和数组S的中位数时,这个式子的值最小,也就是说,我们将S数组从小到大排序,取中位数Sk就是最优解

那么,这道题就迎刃而解了!

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010struct pos
{
int x,y;
} a[MAXN];int i,N,M,T;
long long ans;
long long s[MAXN];inline void solve1()
{
int i;
memset(s,,sizeof(s));
for (i = ; i <= T; i++) s[a[i].y]++;
for (i = ; i <= M; i++) s[i] -= T / M;
for (i = ; i <= M; i++) s[i] += s[i-];
sort(s+,s+M+);
for (i = ; i <= M; i++) ans += abs(s[i] - s[(M+)>>]);
}
inline void solve2()
{
int i;
memset(s,,sizeof(s));
for (i = ; i <= T; i++) s[a[i].x]++;
for (i = ; i <= N; i++) s[i] -= T / N;
for (i = ; i <= N; i++) s[i] += s[i-];
sort(s+,s+N+);
for (i = ; i <= N; i++) ans += abs(s[i] - s[(N+)>>]);
}
int main()
{ scanf("%d%d%d",&N,&M,&T);
for (i = ; i <= T; i++) scanf("%d%d",&a[i].x,&a[i].y);
if (T % N != && T % M != )
{
printf("impossible");
return ;
}
if (T % M == && T % N != )
{
printf("column ");
solve1();
} else if (T % M != && T % N == )
{
printf("row ");
solve2();
} else
{
printf("both ");
solve1();
solve2();
}
printf("%lld\n",ans); return ;}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141149.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:876 阅读:5,464
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,688
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,503
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:731 阅读:4,468
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:5,379
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,263
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站