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

## Re:这样的做法可以证明是正确的吗？

Posted by ym94 at 2019-08-01 10:32:30 on Problem 1230
In Reply To:这样的做法可以证明是正确的吗？ Posted by:harvard at 2005-05-11 16:45:25

AC代码：
/*

*/
#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

#define Max 1010
#define inf 0x3f3f3f3f
#define max(a,b) a>b?a:b;
#define min(a,b) a>b?b:a;

using namespace std;
struct Node{  //优先队列排序
int id;
int cnt;
};
struct cmp{  //从大到小
bool operator()(Node one,Node two)
{
return one.cnt<two.cnt;
}
};
priority_queue<Node ,vector<Node>,cmp> q;  //大根堆
void swap(int &x,int &y)  //交换，因为可能从右到左给数据
{
int c=y;
y=x,x=c;
}
int map[Max][Max]; //保存所有的墙标记
int ok[Max];  //保存墙的数量
int del[Max]; //保存的是是否删除

int main()
{
int t,n,k,stx,sty,endx,endy,x,y,max_y,max_x,ans;
Node temp;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
max_y=-1;
max_x=-1;
ans=0;
memset(map,0,sizeof(map));
memset(del,0,sizeof(del));
memset(ok,0,sizeof(ok));
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&stx,&sty,&endx,&endy);
if(stx>endx) //交换，数据有坑
{
swap(stx,endx);
}
max_x=max(max_x,endx);
max_y=max(max_y,sty);
for(int j=stx;j<=endx;j++)
{
map[sty][j]=i;
}
ok[i]=endx-stx+1;//有多少个墙
}
while(q.size()) q.pop();
for(int i=0;i<=max_x;i++)
{
int laji=0;
for(int j=0;j<=max_y;j++)
{
if(map[j][i]&&!del[map[j][i]])// 有数并且没有被删除
{
laji++;
temp.id=map[j][i];
temp.cnt=ok[temp.id];//还有多少个点
q.push(temp);
}
}
while(q.size()>k)  //一直到全部满足
{
temp=q.top();
q.pop();
ans++;  //每删除一个 ++
del[temp.id]=1; //删除
}
while(q.size())  //点数全部减少
{
temp=q.top();
q.pop();
ok[temp.id]--;
}
}
printf("%d\n",ans);
}
return 0;
}

Followed by: