HDU1735 字数统计

版权声明：长风原创 https://blog.****.net/u012846486/article/details/28011667

字数统计

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的位矩阵(A_ij)（相邻两个数由空格分开），表示被破坏后的作文。当中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;
}