poj 1009 解题心得

March 06, 2013 21:33


过年回来,下班后就去poj.org上做做题, 前天晚上弄到十二点半才把1009过了, Memory: 264K,Time: 79MS,弱爆了, 这里还是写一下心得吧,怎么说也弄到半夜了。。

题目大意就是给出一张图,然后求图中每点与边上的点的最大差值,首先给出图的宽度, 然后就是一堆RLE(run length encoding) 数据,第一个数是值,第一个数是这值的数量, 0 0为图的结束,0是所有输入结束,如:

7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
10
35 500000000
200 500000000
0 0
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0

开始我就直接new出三行图的宽度,然后把输入放入这三行之中,这样三行中的中间一行已经可以找到所有周边的点了, 然后再计算差值,直到我写完,一切感觉良好,然后把代码提交,先是Runtime Error,数据溢出了。。

改改后,再提交,这次没再出运行时错误了,不过超时了,随便写个上万行的,直接就超了,知道问题了就想另外的办法了

想一会后换另一种方法,直接保存所有输入:

#define MAX_LINES 1000

struct RLE {
  unsigned char value;
  int count;
};

RLE rles[MAX_LINES];

题目说了每张图最多1000条数据的,然后直接弄出1000个来了,然后一直写入,等一张图输入完成开始计算, 取得一共有多少行数据,不是rle的条数,而是图的行数,也就是高度,计算差值时点的值我是根据位置, 然后把rles一直加到包含这个点时,这个rle的value就是要取的点的值了

然后就是关键的计算了,如果直接一点一点的算,肯定会超时的,像一些连续的一样的点可以只计算前面的一些, 与最后面的一些,中间的完全是一样的就不用计算了,直接跳过了,像我的代码里就行判断每个rle的点数量是否大于 (图的宽度 + 1) * 2,如果大于的话,中间的就不用计算了,因为中间的四周全是自己一样的点了,差值为0, 然后就是坑爹的只有一行数据的时候,而且这一行数据非常长,10的9次方,这个非常关键,这里面每个rle只要算两边的一点, 中间的数据全是0就不用计算了

按上面的方法我的就直接过了313MS,后面又花了点时间优化了小于等于(图的宽度 + 1) * 2的, 而前面的与面的数据都大于 图的宽度 + 1,这样中间又是一些数据可以不用计算,好的情况就是这个rle的差值全是一样的, 麻烦点的就要计算两边,中间还要分开算,这个弄好后我提交后执行成功掉到74MS

不说了,直接上代码,英文烂,名字取的自然更烂了,注释我试着加上一些:

#include <iostream>
#include <cstdlib>

#define MAX_LINES 1000

using std::cout; using std::cin; using std::endl;

// 定义rle结构
struct RLE {
  unsigned char value;
  int count;
};

class Image {
public:
  Image(int _width){
    width = _width; // 保存图的宽度
    rle_len = 0; // 用来递增保存rle的数量
    pixels = 0; // 用来保存所有点的数量,后面用来计算图的高度
    abs_pixel = -1; // 用来保存差值,当这个值改变时,如果当前不为负就输出RLE,就是结果了
    abs_count = 0; // 差值的数量
  }

  // 用来增加一对rle值
  void write(int pixel, long long count) {
    rle[rle_len].value = pixel;
    rle[rle_len].count = count;
    rle_len += 1;
    pixels += count;
  }


  // 图输入结束,开始计算
  void end() {
    // 计算图的高度
    columns = pixels / width;
    if (pixels % width > 0) { columns += 1; }
    long long pos = 0;
    int rle_count, rle_row;

    // 循环RLE开始计算结果
    for (int i = 0; i < rle_len; i++) {
      // 这里用来判断图是不是只有一行,现在才发现,这个if应该放在for外面。。。
      if (pixels <= width && rle[i].count > 2) {
        pos = count_diff(pos, 1, i);

        add_abs_pixel(0, rle[i].count - 2);
        pos += rle[i].count - 2;

        pos = count_diff(pos, 1, i);
      } else {
        // 不是一行的话,就去计算这个rle
        pos = count_diff(pos, rle[i].count, i);
      }
    }

    add_abs_pixel(-1);
  }

  // 计算一个rle
  long long count_diff(long long pos, long long count, short rle_pos) {
    int min_count_row = width + 1;

    // rle点的数量大于 (图的宽度 + 1) * 2, 中间的可以不用计算了
    if ( count > min_count_row * 2 ) {
      int no_count = count - min_count_row * 2;

      // 边上的点,递归计算
      count_diff(pos, min_count_row, rle_pos);
      count -= min_count_row; pos += min_count_row;

      add_abs_pixel(0, no_count);
      count -= no_count; pos += no_count;
    } else if (same_rle(rle_pos, min_count_row)) {
      // 上面的same_rle用来判断上一个rle和下一个rle的数量是不是大于min_count_row
      // 如果是的话,就又可以少一些计算了

      // 如果大于 图的宽度 + 1 的话计算方法不同了
      if (count > min_count_row) {
        int before = count - min_count_row;

        add_abs_pixel(max_diff(pos), before);
        pos += before; count -= before * 2;

        for (int i = 0; i < count; i++, pos++) {
          add_abs_pixel(max_diff(pos));
        }
        count = before;
      }

      add_abs_pixel(max_diff(pos), count);

      return (pos + count);
    }

    for (int i = 0; i < count; i++, pos++) {
      add_abs_pixel(max_diff(pos));
    }

    return pos;
  }

private:
  RLE rle[MAX_LINES];
  long long width;
  long long rle_len;
  long long pixels;
  int columns;

  int abs_pixel;
  long long abs_count;

  // 这个就不用说了吧。。。上面的注释差不多已经说了
  bool same_rle(long long rle_pos, int min_count_row) { 
    return (rle_pos == 0 || rle[rle_pos - 1].count >= min_count_row) &&
    (rle_pos - 1 == rle_len || rle[rle_pos + 1].count >= min_count_row);
  }

  // 根据位置来取得点的值
  unsigned char get(long long pos) {
    long long tmp = 0;

    for (int i = 0; i < rle_len; i++) {
      tmp += rle[i].count;

      if (pos < tmp) { return rle[i].value; }
    }

    return 0;
  }

  // 计算点与周边的最大差值
  int max_diff(long long pos) {
    int tmp, max = 0;
    int x, y, ox = pos % width, oy = pos / width;
    long long tpos;

    for (int i = -1; i <= 1; i++) {
      for (int j = -1; j <= 1; j++) {
        if (i == 0 && j == 0) { continue; }
        tpos = pos + j * width + i;
        x = ox + i; y = oy + j;

        if (tpos < 0 || tpos >= pixels || x < 0 ||
          x >= width || y < 0 || y >= columns) { continue; }

        tmp = abs(get(pos) - get(tpos));
        if (tmp > max) { max = tmp; }
      }
    }

    return max;
  }

  // 这个用来增加或改变差值的,如果增加的不是相同的,就输入前面的,如果是相同的就直接加数量
  void add_abs_pixel(int pixel, int count = 1) {
    if (abs_pixel != pixel) {
      if (abs_pixel != -1) { out_rle(); }
      abs_pixel = pixel;
      abs_count = count;
    } else {
      abs_count += count;
    }
  }

  void out_rle() {
    cout<<abs_pixel<<" "<<abs_count<<endl;
  }
};


int main() {
  int width, pixel;
  long long count;

  while (cin>>width) {
    if (width == 0) { cout<<"0"<<endl; break; }

    cout<<width<<endl;
    Image img = Image(width);

    while (true) {
      cin>>pixel>>count;

      if (pixel == 0 && count == 0) {
        img.end();
        cout<<"0 0"<<endl;
        break;
      }

      if (count > 0) { img.write(pixel, count); }
    }
  }

  return 0;
}

Comments: