当七夕遇上算法竞赛

2018/8/17  农历 七月初七

今天这个特殊的日子,不知道各位算友都过得怎么样~

适逢七夕,写算法题当然是众汪所归啊!所以今天,我们带来了一道以七夕为背景的题目。

题目:七夕祭(BZOJ3032有权限,可在JoyOI和CodeVS上查找提交)

题目背景:

  七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去TYVJ七夕祭游玩。

题目描述:

  TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多,不过cl只对其中的一部分摊点感兴趣,比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq,希望能够通过恰当地布置会场,使得各行中cl感兴趣的摊点数一样多,并且各列中cl感兴趣的摊点数也一样多。   不过zhq告诉Vani,摊点已经随意布置完毕了,如果想满足cl的要求,唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻,当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间,每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下,至少需要交换多少次摊点。

输入格式:

  第一行包含三个整数N和M和T。T表示cl对多少个摊点感兴趣。   接下来T行,每行两个整数x, y,表示cl对处在第x行第y列的摊点感兴趣。

输出格式:

  首先输出一个字符串。如果能满足Vani的全部两个要求,输出both;如果通过调整只能使得各行中cl感兴趣的摊点数一样多,输出row;如果只能使各列中cl感兴趣的摊点数一样多,输出column;如果均不能满足,输出impossible。   如果输出的字符串不是impossible, 接下来输出最小交换次数,与字符串之间用一个空格隔开。

提示:

  对于30% 的数据,N, M≤100。   对于70% 的数据,N, M≤1000。   对于100% 的数据,1≤N, M≤100000,0≤T≤min(NM, 100000),1≤x≤N,1≤y≤M。

输入样例:

样例输入1 2 3 4 1 3 2 1 2 2 2 3 样例输入2 3 3 3 1 3 2 2 2 3

输出样例:

样例输出1 row 1 样例输出2 both 2

提示:环形均分纸牌、中位数的性质。

思路:

首先我们只要想一想就会发现只要用 t 去模 n和m 就能根据是否整除得到字符串输出是哪个。而且整除的结果就是最后移动后的均摊结果。

然后就可以发现这是个横向和纵向的均分纸牌有木有?(均分纸牌是noip2002的一道经典贪心题目,并不难,希望掌握以后再往下看……不懂记得问)

不加证明地给出行和列分别求就可以了不会影响,因为这一行的点互相交换并不会影响这一列的点的个数。

那我们以行为例:

在均分纸牌中,我们会用a[i] = c[i](实际上这行的数量)-average(均分后的结果)来便于操作,所以a[i]可能是正的也可能是负的,a[i]==0就说明这一行已经达成目标。

而 abs(a[i]) 就是要对这一行进行的操作数,通过前缀和s[i] = a[i] + s[i-1],我们可以通过 ∑mi=1 | s[i] | (m是行数)得到最后所需的总移动次数。

以上为均分纸牌的内容,并没有详细讲。接下来只剩下一个问题了,就是这并不是原来的均分纸牌,此题由于可以画环,所以并不能完全把前缀和 s[i] 加起来就解决了。

此处希望读者在脑中、纸上自行想象如果第一行和最后一行相接会出现怎样的、比常规更巧的分配方式。

然后当我们不知道怎么处理之时神来之笔就是:一定存在一种最优解的方案,环上某两个相邻的人之间没有发生纸牌交换操作。因此我们可以在这里把环断开,就当成从第k+1个人开始依次往下分,像原来一样均分纸牌,一直分到第k个人结束。

普通的均分纸牌是这样的:

我们从第k+1个开始的均分纸牌是这样的:

所以由于s[m]肯定是等于0的,我们所需结果从

变成了

接下来的问题是如果遍历k的话复杂度撑不住。

巧求k,化公式为问题:坐标轴上有m个点,怎样取一个第k点,使得各点到此点的距离之和最短。

结论:1~m个点的坐标排序后的中位数第k个点即是所需点。

简略说明:假如k点左边现在有P个点,右边现在有Q个点,当k点在坐标轴上向右移动一个单位时,左边每个点都远离它一个单位,右边每个点都接近它一个单位,总距离比刚才减少了Q-P个单位;这个过程继续下去,当k为中位点是P=Q,没法再少了,再往右走就过分了,同理得往左走了。

所以回到问题,可以把 s[i] 排序后直接取中位点即可。

至此所有的问题都解决了,如果都理解了的话可以自己动手解决了,如还有没理解可以结合代码看看、搜搜资料、后台留言……最大复杂度(nlogn+mlogm)

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

int n, m, t, flag;
long long ans;
int rows[maxn], columns[maxn];

void solve(int *a, int c)
{
    int average = t / c;
    int s[maxn] = {0};

    for (int i = 1; i <= c; i++)
        a[i] -= average, s[i] = a[i] + s[i-1];
    sort (s+1, s+1+c);
    for (int i = 1; i <= c; i++)
        ans += abs(s[i] - s[(c+1)>>1]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 0; i < t; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        rows[x]++;
        columns[y]++;
    }

    if (t % n == 0)
    {
        flag++;
        solve(rows, n);
    }
    if (t % m == 0)
    {
        flag += 2;
        solve(columns, m);
    }

    if (flag == 0)    printf("impossible");
    else if (flag == 1)    printf("row ");
    else if (flag == 2)    printf("column ");
    else if (flag == 3)    printf("both ");

    if (flag)    printf("%lld", ans);
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-08-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

1113
来自专栏数据结构与算法

P1325 雷达安装

题目描述 描述: 假设海岸线是一条无限延伸的直线。它的一侧是陆地,另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上(包括海岸线),并且每个雷达都...

3426
来自专栏数据结构与算法

P1510 精卫填海

题目描述 【版权说明】 本题为改编题。 【问题描述】 发鸠之山,其上多柘木。有鸟焉,其状如乌,文首,白喙,赤足,名曰精卫,其名自詨。是炎帝之少女,名曰女娃。女娃...

3447
来自专栏章鱼的慢慢技术路

Go指南练习_循环与函数

2252
来自专栏阿凯的Excel

或关系求均值(函数虐心版)

最近醉心于Python的学习和分享,好久没有分享Excel相关的文章了。 熟悉我文章的朋友,都知道我特喜欢分享数组函数,也特喜欢分享那种很长的函数。 前几天有朋...

3926
来自专栏应兆康的专栏

100个Numpy练习【5】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

60610
来自专栏算法修养

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

3314
来自专栏ACM算法日常

四两拨千斤,GCC编译器(同余模) - HDU 3123

同余这一属性看起来简单,然而却是数论中极为重要的概念。与之相关的公式和定理更是纷繁芜杂,如果不是数学背景的童鞋,恐怕很难深入去钻研所有的知识。

832
来自专栏爱撒谎的男孩

回溯算法

2743
来自专栏人工智能

头条官方给不了的圣诞帽,Python和OpenCV给你

随着圣诞的到来,大家纷纷@今日头条给自己的头像加上一顶圣诞帽。当然这种事情用很多P图软件都可以做到。但是作为一个学习图像处理的技术人,还是觉得我们有必要写一个程...

21510

扫码关注云+社区

领取腾讯云代金券