学步园

链接：http://poj.org/problem?id=1009

题意：把题目给出的点的像素值按照给定的要求进行转换，其中转换规则是给出图片宽度width，这些点都是从左到右从上到下一次排

列的，每个点新的像素值是原来的像素值与其前后左右的像素值的差的绝对值最大的那个。

思路:题目给出的点的个数的范围是10^9，width值也没有确定，一个一个的计算空间和时间上都会超的，但是看discuss貌似是说这个

题目的测试数据在width值大于10000时就变成一行，类似这样

100000
2 50000
5 50000
0 0

然后就把这种情况作为特殊情况处理，不过我没试

周围元素都一样的的那些点的对应的新的像素值应该一样，只要碰到一个新的元素，可能会影响到它的周围的这八个元素，其他的

元素只要跟其左边的元素的像素值一样就可以，再根据题目中输入数据的描述，点对x, y 表示y个像素值为x的点，并且点的对数

不超过1000. 不会超内存的，用数组存一下，至于位置，只要稍微计算一下即可。这样就变成寻找每一小段开头的那个点的以及它

周围的八个点的像素值，用一个结构体存一下对应的位置信息，和新的像素值信息，最后对这个结构体数组，按照位置从小到大排

一下序，然后进行输出就行了

代码：47ms，没什么优势

#include
#include
#include
using namespace std;
#define MAX 1005

int data[MAX][2];
int width, tot;
struct Imag{
   int pos;
   int val;
}imag[MAX*9];

bool cmp(const Imag& a, const Imag& b) {
   return a.pos < b.pos;
}

int getval(int pos) {
   int r = (pos - 1)/width;
   int c = (pos - 1)%width;
   int temp = 0, cnt = 0, res = 0;//这块是根据元素所在的位置寻找元素的像素值，我直接挨个寻找，可以二分查找
   while(temp < pos) {
      temp += data[cnt++][1];
   }
   int num = data[cnt - 1][0];
   for(int i = r - 1; i <= r + 1; ++ i) {
      for(int j = c - 1; j <= c + 1; ++ j) {
         int tpos = i*width + j;
         if(i < 0 || j = width || tpos >= tot) {
            continue;
         }
         temp = 0; cnt = 0;
         while(temp  temp ? res : temp;
      }
   }
   return res;
}

int main() {
   freopen("poj1009.txt", "r", stdin);
   while(scanf("%d", &width) && width) {
      printf("%d\n", width);
      int cnt = 0;
      tot = 0;
      while(scanf("%d %d", &data[cnt][0], &data[cnt][1]) && data[cnt][1]) {
         tot += data[cnt][1];
         cnt++;
      }
      int pos = 1, tpos, count = 0;
      for(int k = 0; k <= cnt; ++ k) {
         int r = (pos - 1)/width;
         int c = (pos - 1)%width;
         for(int i = r - 1; i <= r + 1; ++ i) {
            for(int j = c - 1; j <= c + 1; ++ j) {
               tpos = i*width + j;
               if(i < 0 || j = width || tpos >= tot) {
                  continue;
               }
               imag[count].pos = tpos+1;
               imag[count++].val = getval(tpos+1);
            }
         }
         pos += data[k][1];
      }
      sort(imag, imag + count, cmp);
      Imag tmp = imag[0];
      for(int i = 0; i < count; ++ i) {
         if(imag[i].val == tmp.val) {//遇到相同并且连续的像素值需要进行合并
            continue;
         }
         printf("%d %d\n", tmp.val, imag[i].pos - tmp.pos);
         tmp = imag[i];
      }
      printf("%d %d\n", tmp.val, tot - tmp.pos + 1);//处理最后一段
      printf("0 0\n");
   }
   printf("0\n");
}