poj 1009-蒲公英云

poj 1009

参考自大神思路：POJ 1009
首先，暴力必挂，这是题目的善意提醒。
于是，一直在想不暴力的各种判断计算方法，关于各种跳跃移动，后来都无奈想用STL。原谅我的蒟蒻。
再然后就思维混乱了。于是看网上各位大神的解题报告。很神奇的一个搞法。瞬间被震惊。发现了一个道理，有时候从这个角度搞不通的时候，换一个更直接的角度往往一下就搞通了。是的。
首先可以看出来，这个最终的答案中，肯定会有某些连续段，答案是不变的，这些连续段又和原图有关。我自己的思路就是，先找出在原图的某一连续段中，答案值可能改变的几个像素（做标记），再一次次跳跃到这几个像素中计算它们的答案值，但是问题就是，怎么样的像素才是需要计算的像素。
如图的一个map：
在这里插入图片描述

第一个x显然是需要标记的。然后，可以直接跳跃到第4个x，因为此时它的周围多了一个z，答案可能改变，而第二、三个x显然答案和第一个是一样的。再然后，y的第一个也肯定要标记，因为主体变了。然后到了坐标为(2,3)的y，它需要标记是因为它的周围多了一个m。于是以此类推完成。虽然这个搞法看似可以，但这么多的细节要考虑，况且格子数是10^9，以我的水平注定挂。该怎么办呢。在看了各位大神的题解之后，发现其实我只要把需要标记的格子标记出来，并且把每一连续段的分段画出来，就可以发现很神奇的东西：
在这里插入图片描述

紫色标注的都是要标记的格子，红色边框的代表这一个连续段的起始格。我们可以发现，每个连续段的起始格，都是要标记的格子，同时，每个要标记的格子，都是一个连续段起始格的周围8个格子中的一个。所以，改进的搞法就很清楚了：只需要一个个枚举每个连续段的起始格，并计算它和它四周8个格子的答案值，最后统计答案的时候按照位置先后排序，答案中相同的连续段就合并。因为最多只有1000个连续段，所以不管是时间还是空间都不会超。

注意的细节：最后一个位置也为标记的格子。（有关代码在代码行63行）

在这里插入图片描述
为什么最后一个格子是特殊情况？拿上面这个为例子：红色边框的为连续段的起始格，绿色背景的为标注的格子（没考虑最后一个格子）
输入为:
5
10 9
20 11
0 0

如果没有考虑最后一个格子也为标记格子的情况，则有错误输出：
5
0 3
10 17
0 0

考虑最后一个格子的情况，则有正确输出：
5
0 3
0 3
10 12
0 5
0 0

大家可以好好考虑上面这个例子

上代码：

#include<iostream>
#include<cmath>
#include<algorithm>
const int maxn=1005;
using namespace std;
int width,tot;
struct pix
{
    int pos;
    int ans;
}outmap[maxn*8];//记录每个起始格及其8个方向 
int intmap[maxn][2];//[0]存数值，[1]存长度 
int cmp(struct pix p1,struct pix p2)
{
    return p1.pos<p2.pos;
}
int getshu(int p)
{
    int po=0,i=0;
    while(po<=p)
    {
        po+=intmap[i++][1];
    }
    return intmap[i-1][0];
}
int getans(int p)
{
    int r=p/width;
    int c=p%width;
    int ans=0,num=getshu(p);
    for(int i=r-1;i<=r+1;i++)
    {
        for(int j=c-1;j<=c+1;j++)
        {
            int tpos=i*width+j;
            if(j<0||i<0||j>=width||tpos>(tot-1)||tpos==p)
                continue;
            int tmp1=abs(num-getshu(tpos)); 
            if(tmp1>ans) ans=tmp1;
        }
    }
    return ans;
}
int main()
{
    while(cin>>width&&width!=0)
    {
        int num,len,k=0;tot=0;//tot是元素个数 
        while(cin>>num>>len)//录入所有的起始格 
        {
            if(num==0&&len==0)
                break;
            intmap[k][0]=num;
            intmap[k++][1]=len;
            tot+=len;
        }
        //for(int i=0;i<k;i++)
        //    cout<<intmap[i][0]<<" "<<intmap[i][1]<<endl;
        //cout<<k<<endl<<tot<<endl;
        //开始处理
        //cout<<getans(10995)<<endl;
        int post=0,p=0;//pos为起始格的位置 ,p为记录outmap个数 
        for(int i=0;i<=k;i++)//遍历所有的起始格!!!**要考虑最后一个也为标记格子，就要是<=k,而不是<k,为什么是这样，自己拿上面那个例子举例**
        {
            int r=(post)/width;
            int c=(post)%width;
            //cout<<r<<" "<<c<<endl;
            //枚举8个方向
            for(int j=r-1;j<=r+1;j++)
            {
                for(int z=c-1;z<=c+1;z++)
                {
                    int tpos=j*width+z;
                    if(j<0||z<0||z>=width||tpos>(tot-1))
                        continue;
                    //没有出界
                    outmap[p].pos=tpos;
                    outmap[p++].ans=getans(tpos);
                    //cout<<tpos<<" "<<getans(tpos)<<endl;
                }
            }
            //更新post
            post+=intmap[i][1]; 
        }
        //将标记格排序 :按位置从小到大排序 
        sort(outmap,outmap+p,cmp);
        //for(int i=0;i<k;i++)
        //    printf("%d %d\n",outmap[i].pos,outmap[i].ans); 
        struct pix tmp=outmap[0];
        cout<<width<<endl;
        for(int i=1;i<p;i++)
        {
            if(outmap[i].ans==tmp.ans)
                continue;
            printf("%d %d\n",tmp.ans,outmap[i].pos-tmp.pos);
            tmp=outmap[i];
        }  
        printf("%d %d\n",tmp.ans,tot-tmp.pos);
        printf("0 0\n");
    }
    printf("0\n");
    return 0; 
}