比赛 |
20121009 |
评测结果 |
WWWWW |
题目名称 |
木棍 |
最终得分 |
0 |
用户昵称 |
Truth.Cirno |
运行时间 |
0.693 s |
代码语言 |
C++ |
内存使用 |
98.40 MiB |
提交时间 |
2012-10-09 21:22:15 |
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
int l[5010],w[5010],waynum[5010],wayto[5010][5010],innum[5010];
bool used[5010];
int main(void)
{
freopen("wooden.in","r",stdin);
freopen("wooden.out","w",stdout);
int i,j,n,rest,minnum,minpos,pos,to,c=0;
cin>>n;
rest=n;
for (i=1;i<=n;i++)
cin>>l[i]>>w[i];
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (i==j)
continue;
if (l[i]<=l[j]&&w[i]<=w[j])
{
waynum[i]++;
wayto[i][waynum[i]]=j;
innum[j]++;
}
}
while (rest)
{
c++;
minnum=10000;
for (i=1;i<=n;i++)
if (!used[i]&&minnum>innum[i])
{
minnum=innum[i];
minpos=i;
}
while (minnum!=10000)
{
minnum=10000;
pos=minpos;
used[pos]=true;
rest--;
for (i=1;i<=waynum[pos];i++)
{
to=wayto[pos][i];
innum[to]--;
if (!used[to]&&minnum>innum[to])
{
minnum=innum[to];
minpos=to;
}
}
}
}
cout<<c<<endl;
return(0);
}