主题：第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个回复）
沙发
szh [专家分：380] 发布于 2006-07-20 19:43:00
Test
板凳
hwjian [专家分：0] 发布于 2006-07-20 21:41:00
#include<iostream>
using namespace std;
static int Compare(const void *p1, const void *p2)
{
return (*(int *)p1)-(*(int *)p2);
}
int MaxVisitors(int X[], int Y[], int n)
{
int j;
int * a=new int [n*2];
for(j=0;j<n;j++){
a[2*j]=X[j];
a[2*j+1]=Y[j];
}
qsort(a,n,sizeof(int)*2,Compare);
int max(0),temp(0),num;
for(int i=0;i<n;i++)
{
temp=0;
num=a[2*i]+1;
for(j=0;j<n;j++)
if(num>=a[2*j]&&num<a[2*j+1])
temp++;
else{
if(temp>max){
max=temp;
break;
}
else
break;
}
}
return max;
}
3 楼
jjj346 [专家分：0] 发布于 2006-07-20 21:44:00
#include <stdio.h>
#include <string.h>
int MaxVisitors(int x[], int y[], int n)
{
int i,a,max=0,maxt=0;
int z[10000]={0};
for(i=0;i<n;i++)
{
a=x[i];
if(y[i]>maxt)
maxt=y[i];
while(a<y[i])
{
z[a]++;
a++;
}
}
for(i=0;i<maxt;i++)
if(z[i]>max)
max=z[i];
return max;
}
4 楼
火海时代 [专家分：230] 发布于 2006-07-20 22:43:00
#include <iostream>
using namespace std;
int MaxVisitors(int X[], int Y[], int n)
{
int *a;
int i,j;
int l = 0,temp = 0;
for(i = 0; i < n; i++)
if(Y[i] > l)
l = Y[i];
a = new int[l];
for(i = 0; i < l; i++)
a[i] = 0;
for(i = 0; i < n; i++)
for(j = X[i]; j < Y[i]; j++)
a[j-1]++;
for(i = 0; i < l; i++)
if(a[i] > temp)
temp = a[i];
delete []a;
return temp;
}
void main()
{
int X[5] = {1,2,3,4,5};
int Y[5] = {4,4,7,6,9};
cout<<MaxVisitors(X,Y,5)<<endl;
}
5 楼
dongbili [专家分：30] 发布于 2006-07-21 00:00:00
/*用反证法易证，假设在time时刻停的车最多，则必有一个X[i]=time，因此就只须枚举X[i]，找出车辆最多时的车数,如此时间复杂度为O(n^2)*/
int MaxVisitors(int X[], int Y[], int n)
{
int i,j,now,max;/*i，j为循环变量，now为当前车数，max为当前最多车数*/
max=0;
for (i=0;i<n;i++) {
now=0;
for (j=0;j<n;j++)
if (X[i]>=X[j]&&X[i]<Y[j])
now++;
if (max<now)
max=now;
if (max==n)
return n;/*因为只有n辆车，因此可直接返回n*/
}
return max;
}
6 楼
ITER [专家分：680] 发布于 2006-07-21 00:25:00
/****************************************************************
一边游戏挂机 一边编了一个 估计还有错 日后再修改...
****************************************************************/
#include <iostream>
using namespace std;
int time[25]={0};
int MaxVisitors(int X[], int Y[], int n)
{
int i=0;
int j=0;
int tmp=0;
int total=0;
int totalTY=0;
int shizhong=1;
int count=1;
int jihao=0;
for(;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(X[i]>X[j])
{
tmp=X[i];
X[i]=X[j];
X[j]=tmp;
tmp=Y[i];
Y[i]=Y[j];
Y[j]=tmp;
}
}
}
for(i=0;i<n;i++,count=1,shizhong++)
{
jihao=X[i];
time[Y[i]]--;
while(X[i+1]==jihao)
{
count++;
i++;
time[Y[i]]--;
}
totalTY=totalTY+count+time[shizhong];
if(totalTY>total)
total=totalTY;
else if(totalTY<0)
totalTY=0;
}
return total;
}
main()
{
int arrx[]={1,2,4,5,3};
int arry[]={4,4,7,6,9};
cout<<MaxVisitors(arrx,arry,5);
}
7 楼
asddg67 [专家分：1580] 发布于 2006-07-21 09:31:00
#include<iostream.h>
int MaxVisitors(int X[], int Y[], int n);
int find(int X[], int Y[], int n ,int time);
int MaxVisitors(int X[], int Y[], int n)
{
int i;
int max=0;
for(i=0;i<=24;i++)
{
if(find(X,Y,n,i)>max)
{
max=find(X,Y,n,i);
}
}
return max;
}
int find(int X[], int Y[], int n ,int time)
{
int shu=0;
for(int j=0;j<n;j++)
{
if(time>=X[j]&&time<Y[j])
{
shu=shu+1;
}
}
return shu;
}
void main()
{
int number;
int Ctime[10000],Otime[10000];
cout<<"please input the sum number:"<<endl;
cin>>number;
for(int i=0;i<number;i++)
{
cin>>Ctime[i]>>Otime[i];
if(Ctime[i]>Otime[i])
{
cout<<"wrong input:"<<endl;
}
}
cout<<"the max is::"<<MaxVisitors(Ctime,Otime,number)<<endl;
}
8 楼
iAkiak [专家分：8460] 发布于 2006-07-21 09:34:00
#include <vector>
#include <algorithm>
using namespace std;
bool abscmp(const int a, const int b)
{
return abs(a) < abs(b);
}
int MaxVisitors(int X[], int Y[], int n)
{
int i, count = 0, max = 0, lasttime = 0;
vector<int> v(X, X + n);
for (i = 0; i < n; i++)
v.push_back(-Y[i]);
sort(v.begin(), v.end(), abscmp);
for (i = 0; i < v.size(); i++)
{
if (lasttime < abs(v[i]))
{
if (count > max)
max = count;
lasttime = abs(v[i]);
}
v[i] > 0 ? ++count : --count;
}
return max;
}
9 楼
joekings [专家分：550] 发布于 2006-07-21 10:18:00
int MaxVisitors(int X[], int Y[], int n)
{
int i,j,max;
int num[25]={0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0};//用于存放24个时刻的车辆数
for(i=0;i<n;i++)
{
for(j=X[i];j<Y[i];j++) num[j]++;
}
max=0;
for(i=1;i<25;i++)
if(max<num[i]) max=num[i];
return max;
}
//关注这么久了，第一次有会做的题。哈哈，惭愧呀！
10 楼
qqlxinye [专家分：650] 发布于 2006-07-21 11:37:00
int MaxVisitors(int X[], int Y[], int n)
{
int t[2]={0,0};
for(int iT=0;iT<24;iT++)
{
for(int iN=0;iN<n;iN++)
{
if(X[iN]>=iN&&Y[iN]<iN)t[1]++;
}
if(t[0]<t[1])t[0]=t[1];
}
return t[0];
}
int MaxVisitors(int X[], int Y[], int n)
{
int temp=0;
int t[24]={0,0……};
for(int iN=0;iN<n;iN++)
{
for (int i=X[iN];i<Y[iN];i++)
T[i]++;
}
for(int i=0;i<24;i++){if(temp<t[i])temp=t[i];}
return temp;
}
//主要的两种方法都有了，想不出第三种了，等答案。汗……
我来回复
您所在位置：