首页 > 代码库 > HDU1735 字数统计
HDU1735 字数统计
字数统计
Time Limit: 1000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1221 Accepted Submission(s): 315
Problem Description
一天,淘气的Tom不小心将水泼到了他哥哥Jerry刚完成的作文上。原本崭新的作文纸顿时变得皱巴巴的,更糟糕的是由于水的关系,许多字都看不清了。可怜的Tom知道他闯下大祸了,等Jerry回来一定少不了一顿修理。现在Tom只想知道Jerry的作文被“破坏”了多少。
Jerry用方格纸来写作文,每行有L个格子。(图1显示的是L = 10时的一篇作文,’X’表示该格有字,该文有三个段落)。
图1
图2
图2显示的是浸水后的作文 ,‘O’表示这个位置上的文字已经被破坏。可是Tom并不知道原先哪些格子有文字,哪些没有,他唯一知道的是原文章分为M个段落,并且每个段落另起一行,空两格开头,段落内部没有空格(注意:任何一行只要开头的两个格子没有文字就可能是一个新段落的开始,例如图2中可能有4个段落)。
Tom想知道至少有多少个字被破坏了,你能告诉他吗?
Jerry用方格纸来写作文,每行有L个格子。(图1显示的是L = 10时的一篇作文,’X’表示该格有字,该文有三个段落)。
图1
图2
图2显示的是浸水后的作文 ,‘O’表示这个位置上的文字已经被破坏。可是Tom并不知道原先哪些格子有文字,哪些没有,他唯一知道的是原文章分为M个段落,并且每个段落另起一行,空两格开头,段落内部没有空格(注意:任何一行只要开头的两个格子没有文字就可能是一个新段落的开始,例如图2中可能有4个段落)。
Tom想知道至少有多少个字被破坏了,你能告诉他吗?
Input
测试数据有多组。每组测试数据的第一行有三个整数:N(作文的行数1 ≤ N ≤ 10000),L(作文纸每行的格子数10 ≤ L ≤ 100),M(原文的段落数1 ≤ M ≤ 20),用空格分开。
接下来是一个N × L的位矩阵(Aij)(相邻两个数由空格分开),表示被破坏后的作文。其中Aij取0时表示第i行第j列没有文字(或者是看不清了),取1时表示有文字。你可以假定:每行至少有一个1,并且所有数据都是合法的。
接下来是一个N × L的位矩阵(Aij)(相邻两个数由空格分开),表示被破坏后的作文。其中Aij取0时表示第i行第j列没有文字(或者是看不清了),取1时表示有文字。你可以假定:每行至少有一个1,并且所有数据都是合法的。
Output
对于每组测试输出一行,一个整数,表示至少有多少文字被破坏。
Sample Input
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
Sample Output
19
细节要注意。
#include <stdio.h> #include <algorithm> using std::sort; int N, L, M, arr[10002][102], ans, id; struct Node{ int num, pre; } pra[10002]; int getPre(int i){ if(--i == 0) return 0; int j = L; while(arr[i][j] == 0) --j; return L - j; } void addPre(int i){ if(--i == 0) return; int j = L; while(arr[i][j] == 0){ ++ans; arr[i][j] = 1; --j; } } bool cmp(Node a, Node b){ return a.pre < b.pre; } int main(){ int left, right; while(scanf("%d%d%d", &N, &L, &M) == 3){ id = ans = 0; --M; for(int i = 1; i <= N; ++i){ left = L; right = 1; for(int j = 1; j <= L; ++j){ scanf("%d", &arr[i][j]); if(arr[i][j]){ if(j < left) left = j; if(j > right) right = j; } } if(left > 2){ for(int j = 3; j <= right; ++j){ if(arr[i][j] == 0) ++ans, arr[i][j] = 1; } if(i != 1){ pra[id].num = i; pra[id++].pre = getPre(i); } }else{ addPre(i); for(int j = 1; j <= right; ++j){ if(arr[i][j] == 0) ++ans, arr[i][j] = 1; } } } sort(pra, pra + id, cmp); id = id - M; //需要合并的段落数 for(int i = 0; i < id; ++i) ans += pra[i].pre + 2; printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。