Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:想出个更简单的算法

Posted by TangMing at 2009-08-11 10:31:34 on Problem 1230 and last updated at 2009-08-11 11:11:44
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator