主题：第35次编程比赛第一题
szh [专家分：380] 发布于 2006-07-20 19:45:00
近年来，随着私家车的普及，车辆停放这一社会问题日益突出。华东地区某高校由于地处市中心附近，交通便捷，结果若大校区成了社会车辆的免费露天停车场，给学校的治安、管理等各方面带来严重问题。
鉴于这一状况给学校的恶劣影响，学校领导决定出台一系列的规定来对进出校门的车辆进行管理，而在这之前，他们迫切需要有人提供[color=FF0000]一天内究竟最多有多少车辆停放于校内[/color]的报告，以便使出台的规定能适应当前的局面。
我光荣地接受了这项任务，并得到了一份某天的车辆进出时刻记录表。请问我该如何又快又好的解决该问题？
定义函数：int MaxVisitors(int X[], int Y[], int n)
参数说明：X[i]：车辆进校时刻
Y[i]：车辆出校时刻
n：X，Y长度，[color=FF0000]1<=n<=10000[/color]
返回值： 学校内的最多的车辆数目。
[color=FF0000]X[i],Y[i]满足 1=<X[i]<Y[i], 且X[i]和Y[i]一一对应。
[/color]
例如：
下标i 进校时刻 出校时刻
0 1 4
1 2 4
2 4 7
3 5 6
4 3 9
则在3时刻， 有0，1，4停放于校内
5时刻， 有2，3，4停放于校内
所以返回值为3
[color=FF0000] 注意：4时刻，0,1已出学校，因此只有2，4两辆车停放于校内。[/color]
如果有任何问题，请至[url=http://www.programfan.com/club/showbbs.asp?id=182069]关于第35次编程比赛(第1题)[/url]
回复列表 （共29个回复）
21 楼
aoyunlu [专家分：50] 发布于 2006-07-22 09:59:00
上班在公司写了下，没编译，不晓得对不。
//该函数没有判断停车过夜的情况
int MaxVisitors(int x[],int y[],int n)
{
int MaxParking,dayHour[24];
MaxParking=0;
int i,j;
for (i=0;i<n;i++)
for (j=x[i];j<y[i];j++)
++dayHour[i+1];//*记录进入和出去的时间段，并把这个时间段用dayhour[]保存下来*//
for (i=1,i<24,i++)
MaxParking=MaxParking<day[i]?day[i]:MaxParking;
return MaxParking;
}
22 楼
清月流 [专家分：0] 发布于 2006-07-22 11:30:00
#include <iostream.h>
int MaxVisitors(int X[], int Y[], int n,int t)
{
int counter=0;
for(int i=0; i<n; i++)
{
if (X[i]<=t)
if (Y[i]>t)
counter++;
}
return counter;
}
void main()
{
const int n=5;
int X[n]={1,2,4,5,3},Y[n]={4,4,7,6,9};
for(int i=0; i<24; i++)
cout<<"The time "<<i<<" have "<<MaxVisitors(X,Y,n,i)<<" cars."<<endl;
}
24 楼
spacewei [专家分：270] 发布于 2006-07-22 14:10:00
#include <vector>
using std::vector;
using std::vector<int>;
int MaxVisitors(int X[], int Y[], int n)
{
int maxv=0,tmin=X[0],tmax=Y[0];
for (int i=1;i!=n;++i)
{
if(tmin>X[i]) tmin=X[i];
if(tmax<Y[i]) tmax=Y[i];
}
vector<int> t(tmax-tmin+1,0);
for(int j=0;j!=n;++j)
for(vector<int>::size_type k=X[j];k!=Y[j];++k)
if(maxv<(++t[k-tmin])) maxv=t[k-tmin];
return maxv;
}
25 楼
dongbili [专家分：30] 发布于 2006-07-22 14:47:00
/*排序+DP*/
struct node {
int sta,beg,end,num,ans;
};
int MaxVisitors(int X[],int Y[],int n)
{
struct node a[2*n];
int i,max=1;
void quick_sort(struct node a[],int l,int r);
for (i=0;i<n;i++) {
a[2*i].sta=1;
a[2*i].num=X[i];
a[2*i+1].sta=0;
a[2*i+1].num=Y[i]-1;
}
quick_sort(a,0,n-1);
a[0].beg=a[0].sta;
a[0].end=0;
a[0].ans=1;
for (i=1;i<2*n;i++) {
a[i].beg=a[i-1].beg+a[i].sta;
a[i].end=a[i-1].end+(1-a[i-1].sta);
a[i].ans=(a[i].num==a[i-1].num)?(a[i-1].ans+1):(a[i].beg-a[i].end);
if (max<a[i].ans)
max=a[i].ans;
if (max==n)
return n;
}
return max;
}
void quick_sort(struct node a[],int l,int r)
{
int m;
int partition(struct node a[],int l,int r);
if (l<r) {
m=partition(a,l,r);
quick_sort(a,l,m-1);
quick_sort(a,m+1,r);
}
}
int partition(struct node a[],int l,int r)
{
int x,i,j;
void swap(struct node *a,struct node *b);
x=a[r].num;
i=l-1;
for (j=l;j<r;j++)
if (a[j].num<=x)
swap(&a[++i],&a[j]);
swap(&a[++i],&a[r]);
return i;
}
void swap(struct node *a,struct node *b)
{
struct node c;
c=*a;
*a=*b;
*b=c;
}
26 楼
fenix124 [专家分：70] 发布于 2006-07-22 16:01:00
随便写着玩的
开个大数组,记录来车的所有可能时间
int C[MAXTIME];
int X[MAX];
int Y[MAX];
int N;
int solve()
{
int i,j,max;
for(i = 0;i < N;i++)
for(j = X[i];j <= Y[i];j++) C[j]++;
max = 0;
for(i = 0;i < MAXTIME;i++)
if(C[i] > max) max = C[i];
memset(C,0,MAXTIME*4);
return max;
}
27 楼
lizr2006 [专家分：20] 发布于 2006-07-22 16:07:00
/*第35次编程比赛第一次：*/
#include <iostream.h>
#include <assert.h>
/*MaxVisitors函数接口如下：*/
int MaxVisitors( int X[], int Y[], int n)
{
int num[24] = { 0 };
int max = 0;
for ( int i=0; i<n; i++ )
{
int t = X[i];
while ( t < Y[i] )
{
num[t++]++;
}
}
for ( int j=0; j<24; j++ )
{
if ( max < num[j] )
{
max = num[j];
}
}
return max;
}
/*测试函数，在VC6.0下运行*/
int main()
{
int n;
cin >> n;
int *x = new int[n];
assert( x != NULL );
int *y = new int[n];
assert( y != NULL );
for ( int i=0; i<n; i++ )
{
cin >> x[i] >> y[i];
}
cout << MaxVisitors(x, y, n) << endl;
return 0;
}
28 楼
太没劲了 [专家分：2050] 发布于 2006-07-22 17:19:00
tested under vc6
struct _dwaynode
{
void *prev;
void *next;
int x;
int y;
int n;
};
#define NEWNODE(NODE, _X,_Y) do { NODE=(struct _dwaynode *)calloc(1,sizeof(struct _dwaynode)); NODE->x = _X; NODE->y=_Y; NODE->n=1; } while(0)
#define INSERTPREV(_CUR,_PREV) do { ((struct _dwaynode *)_CUR->prev)->next = _PREV; _PREV->prev = _CUR->prev; _PREV->next = _CUR; _CUR->prev = _PREV; } while(0)
#define INSERTNEXT(_CUR,_NEXT) do { if( _CUR->next ) ((struct _dwaynode *)_CUR->next)->prev = _NEXT; _NEXT->prev = _CUR; _NEXT->next = _CUR->next; _CUR->next = _NEXT; } while(0)
void dealit(struct _dwaynode *cur,struct _dwaynode *new)
{
struct _dwaynode *newnode,*refnode=NULL,*curnode;
if( !cur->x )
{
if( !cur->next )
{
cur->next = new, new->prev = cur;
return;
}
else cur = cur->next;
}
curnode = cur;
if( new->x <cur->x )
{
if( new->y <= cur->x ) INSERTPREV(cur,new);
else /* y>x */
{
NEWNODE(newnode,new->x,cur->x);
INSERTPREV(cur,newnode);
new->x = cur->x;
dealit(cur,new);
}
}
else if( new->x == cur->x )
{
if( new->y<cur->y )
{
INSERTNEXT(cur,new);
new->n = cur->n, ++cur->n;
new->x = new->y, new->y = cur->y, cur->y = new->x;
}
else if( new->y == cur->y )
{
++cur->n;
free(new);
}
else /* > */
{
++cur->n;
new->x = cur->y;
refnode = new;
}
}
else /* > */
{
if( new->x >= cur->y )
refnode = new;
else if( new->y>= cur->y )
{
int keepy;
keepy = new->y;
INSERTNEXT(cur,new);
new->n = cur->n+1, new->y = cur->y, cur->y = new->x;
if( keepy>new->y )
{
NEWNODE(newnode,new->y,keepy);
refnode = newnode, curnode = new;
}
}
else /* < */
{
NEWNODE(newnode,new->y,cur->y);
newnode->n = cur->n, new->n = cur->n+1;
cur->y = new->x;
newnode->next = cur->next, cur->next = new, new->prev = cur;
new->next =newnode, newnode->prev = new;
}
}
if( refnode )
{
if( !curnode->next ) curnode->next = refnode, refnode->prev = curnode;
else dealit(curnode->next,refnode);
}
}
int MaxVisitors(int X[], int Y[], int n)
{
int i,maxnum;
struct _dwaynode *cur,*prev;
struct _dwaynode *head;
NEWNODE(head,0,0);
for(i=0;i<n ;++i)
{
NEWNODE(cur,X[i],Y[i]);
dealit(head,cur);
}
for(maxnum=0, cur=head; cur;prev = cur,cur = cur->next)
{
if( !cur->x ) continue;
if( cur->n > maxnum ) maxnum = cur->n;
free(prev);
}
free(prev);
return(maxnum);
}
29 楼
xyhx [专家分：0] 发布于 2006-07-22 18:41:00
int MaxVisitors(int X[], int Y[], int n)
{
int i,time=1;
int num,count;
int maxtime=0;
for(i=0;i<n;i++)
if (maxtime<Y[i])
maxtime=Y[i];
for(time=1;time<maxtime;time++)
{
num=0;
for(i=0;i<n;i++)
if (time>=X[i] && time<Y[i])
num++;
if (count<num)
count=num;
}
return(count);
}
我来回复
您所在位置：