POJ 1230 Pass-Muraille#贪心+vector迭代器用法

(~ ̄▽ ̄)~*

(注意下面代码中关于iterator的用法,此代码借鉴某大牛)

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std; struct Wall
{
int row;//表示墙在哪行
int left;
int right;
}; int col[105];//保存每列的墙数
vector<Wall> wall; int main()
{
int t,n,k,ax,ay,bx,by;
scanf("%d",&t);
while(t--)
{
wall.clear();
memset(col,0,sizeof(col));
scanf("%d%d",&n,&k);
int maxright=0;
int cnt=0;
while(n--)
{
scanf("%d%d%d%d",&ax,&ay,&bx,&by);
if(ax>bx)
swap(ax,bx);//有可能先输入墙的右端点
if(bx>maxright)
maxright=bx; Wall temp;
temp.row=ay; temp.left=ax; temp.right=bx;
wall.push_back(temp);
for(int i=ax;i<=bx;i++)
col[i]++;
}
int maxt;
for(int i=0;i<=maxright;i++)
{//前面maxright记录了所有墙中的最右端,这样遍历的时候,在maxright结束即可
while(col[i]>k)
{//遍历每列,当该列的墙数>k,说明需要删墙了
vector<Wall>::iterator it=wall.begin();//遍历迭代器
vector<Wall>::iterator iter;//临时迭代器
maxt=0;
while(it!=wall.end())
{//把右边界最大(right大于maxt)的墙(用iter记录)删掉(erase vector元素wall中的第iter个元素)
if((*it).left<=i)
{
if((*it).right>maxt)
{
maxt=(*it).right;
iter=it;
}
}
it++;
}
for(int j=(*iter).left;j<=(*iter).right;j++)
col[j]--;//删掉墙相关的记录
wall.erase(iter);//删掉墙
cnt++;
}
}
printf("%d\n",cnt);
}
return 0;
}
上一篇:Linux 安装SVN服务器 (转)


下一篇:C++vector迭代器失效的问题