#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
const int size = 1000;
const int out_size = 8000;
int pairs[size][2];
int output[out_size][2]; 
int mmax(int a, int b){
	return a > b ? a : b;
}
int abss(int a, int b){
	if (a > b) return a - b;
	else return b - a;
}
int width = 0;
int pixel_num = 0;
int len = 0;
int out_len = 0;
int height = 0;
int cache[out_size];
int get_value(int pos){
	int i = 0, j = 0;
	while (j < pos){
		j += pairs[i++][1];
	}
	return pairs[i-1][0];	
}
int get_max(int pos){
	int row = (pos-1) / width;
	int col = (pos-1) % width;
	int p = get_value(pos);
	int max12 = 0;
	for (int i = row - 1; i < row + 2;i++){
		for (int j = col - 1; j < col + 2;j++){
			int tmp_pos = i*width + j;
			if (i < 0 || j < 0 || j >= width || (i == row && j == col) || tmp_pos >= pixel_num) continue;
			int v = get_value(tmp_pos+1);
			//cout << "p: " << p << " v: " << v << endl;
			max12 = mmax(max12, abss(p, v));
		}
	}
	//cout <<"row:"<<row<<" col:"<<col<< " max : " << max12 << endl;
	return max12;
}
void exchange(int arr[out_size][2], int i, int j){
	int t[2];
	t[0] = arr[j][0];
	t[1] = arr[j][1];
	arr[j][0] = arr[i][0];
	arr[j][1] = arr[i][1];
	arr[i][0] = t[0];
	arr[i][1] = t[1];
}
int partition(int arr[out_size][2], int p, int r){
	int i = p - 1;
	int pivot = arr[r][0];
	for (int j = p; j < r; j++){
		if (arr[j][0] < pivot){
			i++;
			exchange(arr, i, j);
		}
	}
	exchange(arr, i+1, r);
	return i + 1;
}
void quicksort(int arr[out_size][2], int p, int r){
	if (p < r){
		int q = partition(arr, p, r);
		quicksort(arr, p, q - 1);
		quicksort(arr, q + 1, r);
	}
}
int main(){
	//freopen("Text.txt", "r", stdin);
	int value, num;	
	width = 0;
	while (cin >> width && width != 0){		
		len = 0;
		pixel_num = 0;
		out_len = 0;		
		while (cin >> value >> num && num > 0){	
			pairs[len][0] = value;
			pairs[len++][1] = num;
			pixel_num += num;
		}

		height = pixel_num / width;
		int pos = 1;
		int index = 0;
		for (int p = 0; p < len; p++){			
			int row = (pos -1) / width;
			int col = (pos -1) % width;
			for (int i = row - 1; i < row + 2; i++){
				for (int j = col - 1; j < col + 2; j++){
					int tmp_pos = i*width + j;
					if (i < 0 || j < 0 || tmp_pos >= pixel_num) continue;					
					output[index][0] = tmp_pos+1;					
					int v = get_max(tmp_pos+1);									
					output[index++][1] = v;
				}
			}
			pos += pairs[p][1];
		}

		///head point at the last line
		int tmp_pos = (height-1)*width;		
		output[index][0] = tmp_pos+1;
		output[index++][1] = get_max(tmp_pos+1);		

		///last point at the last line	
		tmp_pos = pixel_num - 1;		
		output[index][0] = tmp_pos;
		output[index++][1] = get_max(tmp_pos);		
		quicksort(output, 0, index-1);
		/*
		cout << "================================================" << endl;
		for (int i = 0; i < index; i++){
			cout << output[i][0] << "  " << output[i][1] << endl;
		}
		cout << "================================================" << endl;
		*/
		cout << width << endl;
		int res_value = output[0][1];
		int start_pos = 1;
		for (int i = 0; i < index; i++){
			if (output[i][1] == res_value) continue;			
			cout << res_value << " " << output[i][0] - start_pos<< endl;
			start_pos = output[i][0];
			res_value = output[i][1];			
		}
		cout << res_value << " " << pixel_num - start_pos +1<< endl;
		cout << "0 0" << endl;
	}
	cout << "0" << endl;
	return 0;
}

• Re:总是wrong answer, 求大神帮忙看看 (3788) fnoizfwang 2019-05-12 11:30:12