字数统计
- 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 想知道至少有多少个字被破坏了, 你能告诉他吗?
?
Input
測试数据有多组. 每组測试数据的第一行有三个整数: N(作文的行数 1 ≤ N ≤ 10000).L(作文纸每行的格子数 10 ≤ L ≤ 100),M(原文的段落数 1 ≤ M ≤ 20), 用空格分开.
接下来是一个 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;
- }
来源: http://www.bubuko.com/infodetail-3008927.html