首页 > ACM题库 > HDU-杭电 > HDU 1735 字数统计-贪心-[解题报告] C++
2013
12-21

HDU 1735 字数统计-贪心-[解题报告] C++

字数统计

问题描述 :

  一天,淘气的Tom不小心将水泼到了他哥哥Jerry刚完成的作文上。原本崭新的作文纸顿时变得皱巴巴的,更糟糕的是由于水的关系,许多字都看不清了。可怜的Tom知道他闯下大祸了,等Jerry回来一定少不了一顿修理。现在Tom只想知道Jerry的作文被“破坏”了多少。
  Jerry用方格纸来写作文,每行有L个格子。(图1显示的是L = 10时的一篇作文,’X’表示该格有字,该文有三个段落)。

图1

图2

  图2显示的是浸水后的作文 ,‘O’表示这个位置上的文字已经被破坏。可是Tom并不知道原先哪些格子有文字,哪些没有,他唯一知道的是原文章分为M个段落,并且每个段落另起一行,空两格开头,段落内部没有空格(注意:任何一行只要开头的两个格子没有文字就可能是一个新段落的开始,例如图2中可能有4个段落)。
  Tom想知道至少有多少个字被破坏了,你能告诉他吗?

输入:

  测试数据有多组。每组测试数据的第一行有三个整数:N(作文的行数1 ≤ N ≤ 10000),L(作文纸每行的格子数10 ≤ L ≤ 100),M(原文的段落数1 ≤ M ≤ 20),用空格分开。
  接下来是一个N × L的位矩阵(Aij)(相邻两个数由空格分开),表示被破坏后的作文。其中Aij取0时表示第i行第j列没有文字(或者是看不清了),取1时表示有文字。你可以假定:每行至少有一个1,并且所有数据都是合法的。

输出:

  对于每组测试输出一行,一个整数,表示至少有多少文字被破坏。

样例输入:

10 10 3
0 0 0 1 1 1 0 1 1 0
1 1 0 0 0 1 1 1 0 0
0 0 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 0 0 0
1 1 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 0

样例输出:

19

贪心,只要开头有两个0,则需要判断其上一行最后有多少个连续的0,按上一行最后处0的数量由大到小排序(因为要令破坏字数最小,因此需要令其可转换为1(即可确定的字数)的0的数量最大)。最后特殊处理一下,第一行开头和最后一行结尾的0即可。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;

int mess[10001][101];
struct Tom
{
    int num, zero;
} save[10001];
int cmp(const void *x, const void *y)
{
    return (*(struct Tom*)y).zero - (*(struct Tom*)x).zero;
}
int main()
{
#ifdef test
    freopen("sample.txt", "r", stdin);
#endif
    int m, n, l;
    while(scanf("%d%d%d", &n, &l, &m) != EOF)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<l; j++)
                scanf("%d", &mess[i][j]);
        }
        int cct=0;
        if(mess[0][0]==0&&mess[0][1]==0)
            mess[0][0]=mess[0][1]=2;// 文章开头段 0 的处理
        for(int i=1; i<n; i++)
            if(mess[i][0]==0&&mess[i][1]==0)
            {
                save[cct].num = i;
                save[cct].zero = 0;
                for(int j=l-1; j>=0; j--)
                    if(mess[i-1][j]==0)
                        ++save[cct].zero;
                    else break;
                ++cct;
            }
        qsort(save, cct, sizeof(save[0]), cmp);
        for(int i=0; i<m-1; i++)
        {
            int ii = save[i].num;
            mess[ii][0]=mess[ii][1]=2;// 令段头的0全部转换为1
            for(int j=l-1; j>=0; j--)
                if(mess[ii-1][j]==0)
                    mess[ii-1][j] = 2;// 令段尾部的0全部转换为1
                else break;
        }
        int cct_zero=0;
        for(int i=l-1; i>=0; i--)
            if(mess[n-1][i]==0)// 文章结尾处0的处理
                mess[n-1][i]=2;
            else break;
        for(int i=0; i<n; i++)
            for(int j=0; j<l; j++)
                if(mess[i][j]==0)
                    ++cct_zero;
        printf("%d\n", cct_zero);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/goomaple/article/details/8566148


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }