| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:想出个更简单的算法In Reply To:Re:想出个更简单的算法 Posted by:without2002 at 2008-07-19 19:06:00 > I have tried ,but RE,...代码如下,,Why runtime error
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
int walls[1005];
struct Info
{
int c1,c2;
bool operator <(const Info &a)const
{
return c2>a.c2;
}
};
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int min(int a,int b)
{
if(a<b)return a;
return b;
}
int main()
{
multiset<Info>se;
//freopen("aaa.txt","r",stdin);
int ca,i,k,n,j,column=0,y1,y2,x1,x2,sum=0;
scanf("%d",&ca);
while(ca--)
{
scanf("%d%d",&n,&k);
memset(walls,0,sizeof(walls));
for(i=0;i<n;i++)
{
Info one;
scanf("%d%d%d%d",&y1,&x1,&y2,&x2);
one.c2=max(y1,y2);
one.c1=min(y1,y2);//起点
if(one.c2>column)column=one.c2;
for(int kk=one.c1;kk<=one.c2;kk++)
walls[kk]++;
se.insert(one);
}
sum=0;
for(i=0;i<=column;i++)
{
if(walls[i]>k)
{
int del=walls[i]-k;//需要删除del条
sum+=del;
multiset<Info>::iterator it;
it=se.begin();
int havedel=0;
for(;it!=se.end();it++)
{
if((*it).c1<=i)
{
for(j=i;j<=(*it).c2;j++)
walls[j]--;
havedel++;
se.erase(it);
if(havedel==del)break;
}
}
}
}
printf("%d\n",sum);se.clear();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator