poj1083解题报告

时间：2010-07-18 来源：godfrey90

1.算法
对每组数据进行求解。首先读入一组数据，通过一个结构体数组记录这组数据，然后将这组数据进行排序，排序算法是根据结构体中的s，若s相同则按照t排序。对排序后的数据一遍一遍的从左往右扫描，每扫描一遍可以完成多次不冲突的搬运，每次扫描的时间为10，一直扫描下去，直到所有的搬运完成，便可算出一共要的时间。
注意：题目中没有说对应的s和t有s<=t，所以如果s>t要调换位置。
2.实现
(1)同样用到了标准库qsort函数，在之前要include<stdlib>。
(2)结构体中的数据在内存中的位置是连续的，整个结构体的大小为结构体中各项数据大小的和。体现在在qsort的第3个参数为每个结构体的大小（即结构体中各数据的大小和）还有比较函数com中在比较结构体中的第二个数据的时候可用*((int*)a+1)来访问。
3.代码

#include<cstdio>
#include<cstdlib>
struct ST
{
int s;
int t;
};
int com(const void* a,const void* b)
{
int result = *(int*)a-*(int*)b;
if(result==0) result=*((int*)a+1)-*((int*)b+1);
return result;
}
int main()
{
int result[1000]={0};
int size_of_result=0;
int T;
scanf("%d",&T);
for (int i=0;i<T;i++)
{
/*对第i组数据进行读取计算处理*/
int n;
ST st[200];
//读取第i组中的n个数据并对这n个数据依据s排序
scanf("%d",&n);
for(int j=0;j<n;j++)
{
scanf("%d%d",&st[j].s,&st[j].t);
if(st[j].s>st[j].t)
{
int temp = st[j].s;
st[j].s = st[j].t;
st[j].t = temp;
}
}
qsort((void*)st,n,2*sizeof(int),com);

//对第i组中的数据进行处理
int done_n=0;
bool done[200]={false};
int tail=0;

while(done_n!=n)
{
tail=0;
for(int j=0;j<n;j++)
{
if((!done[j])&&((st[j].s+1)/2>tail))
{
tail=(st[j].t+1)/2;
done[j]=true;
done_n++;
}
}
result[size_of_result]++;
}
size_of_result++;
}
for(int i=0;i<size_of_result;i++)
{
printf("%d\n",result[i]*10);
}
return 0;
}

ps：看到别人的一个比较好的算法

> 把过道分成200份,定义一个整型数组统计每块过道上搬运经过的次数,
> 最后排序,输出最大的次数乘以10即可!
>
> #include<iostream>
> #include<algorithm>
> using namespace std;
> int main()
> { int n,num,a[200][2],b[200];
> cin>>n;
> while(n--)
> {cin>>num;
> for(int m=0;m<200;m++)
> b[m]=0;
>   for(int i=0;i<num;i++)
>   {cin>>a[i][0]>>a[i][1];
>    if(a[i][0]>a[i][1])
>    {int temp=a[i][0];a[i][0]=a[i][1];a[i][1]=temp;}
>   }
>   for(int j=1;j<=200;j++)
> for(int k=0;k<num;k++)
>   if((((a[k][0])<=2*j-1)&&((a[k][1])>=2*j-1)||(((a[k][0])<=2*j)&&((a[k][1])>=2*j))))
>   b[j-1]++;
>   sort(&b[0],&b[200]);
>   if(b[199]!=0) cout<<b[199]*10<<endl;
>   else cout<<'10'<<endl;
> }
> return 0;
> }