F:百科蝌蚪团
时间限制:
1000ms
内存限制:
65536kB
描述
百度百科有一支神奇的队伍，他们叫自己“百科蝌蚪团”。为了更好的让蝌蚪团的成员们安排工作，百度百科的运营团队定出了一个24小时制的时间表。例如：
1. 每个蝌蚪团成员工作时长相同；
2. 必须安排蝌蚪团成员在他们方便的时间段工作；
3. 蝌蚪团成员安排时间最小安排时间节点（开始工作或停止工作）为半小时，比如04：00或04：30，而不是04：15；
4. 蝌蚪团成员一天在百度百科工作的时间是有上限的，他们会根据自己的情况给出上限。
5. 在特定时间段内必须有一定数量的蝌蚪团成员工作，以保证百度百科不断的进步
请帮运营团队计算一下，能保持24小时稳定在岗的蝌蚪团最少成员的数量。如果有2个蝌蚪团成员工作结束，同时另2个蝌蚪团成员开始工作，这段时间都算有2各成员稳定在岗。
输入
输入有多组，每组测试数据以一个整数N开头（1 ≤ N ≤ 50），表示蝌蚪团的成员数。紧接着，我们会有N个数据块，每一个数据块对应了一名蝌蚪团成员的日程情况。
每个数据块以两个整数开始，分别为K（1 ≤ K ≤ 50）和M（1 ≤ M ≤ 1440），用空格隔开。K表示这个数据块对应蝌蚪团成员方便的时间段的数量，M表示这个成员愿意每天在百度百科工作的最长分钟数。接下去的K行中，每行包括两个时间，分别表示成“HH：MM”的格式，以空格分隔，分别对应了该蝌蚪团成员一个方便的时间段的开始时间、结束时间；例如09：00
10：00表明他在早上九点到十点的时间段是方便的，可以在百度百科工作。如果两个时间相同，则说明这个他全天都是方便的。
最后一组数据的N为0，表示输入结束。
输出
对于每组数据，输出为一个整数，占一行。表示能保持24小时稳定在岗的蝌蚪团最少成员的数量。
样例输入
5
1 720
18:00 12:00
1 1080
00:00 23:00
1 1080
00:00 20:00
1 1050
06:00 00:00
1 360
18:00 00:00
3
1 540
00:00 00:00
3 480
08:00 10:00
09:00 12:00
13:00 19:00
1 420
17:00 00:00
3
1 1440
00:00 00:00
1 720
00:00 12:15
1 720
12:05 00:15
0
样例输出
2
1
1
【答案未通过】
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(void)
{
intblockNums = 0;
intcountOfTimeSegment = 0; //k
intmaxMinutesOfMember = 0; //m
stringbeginTimeOfMember; //beginTime
stringendTimeOfMember; //endTime
int*pBlockArr = NULL;
int*pMaxMinute = NULL;
pair<string,string> timePairs;
vector<pair<string,string> > tVec;
vector<pair<string,string> >::iterator iter;
boolbOnlyOne = false;
intminMemberCnt = 0; //输出结果，最小成员数...
while(cin >> blockNums )
{
if(blockNums== 0)
{
break;
}
pBlockArr= new int[blockNums];
pMaxMinute= new int[blockNums];
for(int i=0; i< blockNums; i++ )
{
cin>> pBlockArr[i] >> pMaxMinute[i];
if(pBlockArr[i] != 0)
{
for(int j = 0; j < pBlockArr[i]; j++)
{
cin>> beginTimeOfMember >> endTimeOfMember;
timePairs= make_pair(beginTimeOfMember,endTimeOfMember);
tVec.push_back(timePairs);
iter= tVec.begin();
while( iter != tVec.end() )
{
if(iter->first== iter->second)
{
minMemberCnt= 1;
bOnlyOne= true;
break;
}
++iter;
}
}
}//endif
}//endfor
if(!bOnlyOne)
{
intiSize = tVec.size();
cout<< "iSize = " << iSize << endl;
inttempVal = 0;
intiCnt = 0;
for(int i = 0; i < iSize; i++ )
{
if((tVec[i].first == "00:00") || (tVec[i].second == "00:00") )
{
++iCnt;
tempVal+= pMaxMinute[i];
if(tempVal>= 24*60)
{
break;
}
}
}
minMemberCnt= iCnt;
}
cout<< minMemberCnt << endl;
}//endwhile
return0;
}
【网友通过】
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#include<memory.h>
#define maxn 102
#define MAX 0xfffffff
int d[maxn],g[maxn][maxn],f[maxn][maxn],pre[maxn],map[maxn][maxn],sum[maxn],current[maxn];
int n,m,num,mm;
struct node
{
int x,y;
}seg[1000],mytime[1000];
int cmp(const node &a,const node &b)
{
return a.x<b.x;
}
void rev_bfs(int t)
{
int queue[maxn],flag[maxn];
int head,tail,i;
memset(sum,0,sizeof(sum));
for (i=0;i<=n+49;++i)
{
d[i]=n+49;
sum[n+49]++;
}
sum[n+49]--;
sum[0]++;
d[t]=0;
queue[1]=t;
flag[t]=1;
head=1;tail=1;
memset(flag,0,sizeof(flag));
while (head<=tail)
{
for (i=0;i<=n+49;++i)
if (flag[i]==0&&g[i][queue[head]]>0)
{
queue[++tail]=i;
d[i]=d[queue[head]]+1;
sum[n+49]--;
sum[d[i]]++;
flag[i]=1;
}
head++;
}
}
void augment(int s,int t)
{
int i,min;
min=MAX;
for (i=t;i!=s;i=pre[i])
if (g[pre[i]][i]<min)
min=g[pre[i]][i];
for (i=t;i!=s;i=pre[i])
{
g[pre[i]][i]-=min;;
g[i][pre[i]]+=min;
f[pre[i]][i]+=min;
f[i][pre[i]]-=min;
}
}
int retreat(int *u,int s)
{
int v,min;
min=n+49;
for (v=0;v<=n+49;++v)
if (g[*u][v]>0&&d[v]<min)
min=d[v];
sum[d[*u]]--;
if ((sum[d[*u]])==0&&d[*u]<=n+49)
return 0;
d[*u]=min+1;
sum[d[*u]]++;
current[*u]=0;
if (*u!=s)
*u=pre[*u];
return 1;
}
void ISAP(int s,int t)
{
int u,v;
rev_bfs(t);
u=s;
while (d[s]<n+50)
{
for (v=current[u];v<=n+49;v++)
if (g[u][v]>0&&d[u]==d[v]+1)
break;
if (v<=n+49)
{
current[u]=v;
pre[v]=u;
u=v;
if (u==t)
{
augment(s,t);
u=s;
}
}
else if(retreat(&u,s)==0)
return;
}
}
void solve()
{
int i,j,a,b,c,d,min,t,k,ans,max,st,en,temp;
while(scanf("%d",&n)!=EOF)
{
if(!n) break;
memset(map,0,sizeof(map));;
for (i=1;i<=n;++i)
{
scanf("%d %d",&m,&t);
map[48][i+48]=t/30;
num = mm = 0;
for(j=1;j<=m;++j)
{
scanf("%d:%d %d:%d",&a,&b,&c,&d);
if (a==c && b==d)
{
for (k=0;k<48;++k)
map[i+48][k]=1;
continue;
}
if (!c && !d)
{
++num;
seg[num].x=a*60+b , seg[num].y=1440;
}
else if (a*60+b>c*60+d)
{
++num;
seg[num].x=a*60+b , seg[num].y=1440;
++num;
seg[num].x=0 , seg[num].y=c*60+d;
}
else
{
++num;
seg[num].x=a*60+b , seg[num].y=c*60+d;
}
}
if(num==0)
continue;
sort(seg+1,seg+num+1,cmp);
st=seg[1].x;
en=seg[1].y;
seg[num+1].x=1500;
seg[num+1].y=1600;
for (j=2;j<=num+1;++j)
{
a=seg[j].x;
b=seg[j].y;
if (st<=a && a<=en&&en<b)
en=b;
else if(a>en)
{
mm++;
mytime[mm].x=st , mytime[mm].y=en;
st=a;
en=b;
}
}
for (j=1;j<=mm;++j)
{
a=mytime[j].x/60;
b=mytime[j].x-60*a;
c=mytime[j].y/60;
d=mytime[j].y-60*c;
if (a==c)
{
if (b==0&&d>=30)
map[i+48][a*2]=1;
}
else
{
if (b>0&&b<=30)
b=30;
if (b>30)
{
a++;
b=0;
}
if (d<30)
d=0;
if (d>30)
d=30;
while (a!=c||b!=d)
{
map[i+48][a*2+b/30]=1;
b+=30;
if (b==60)
{
a++;
b=0;
}
}
}
}
}
max=MAX;
for (j=0;j<48;++j)
{
temp=0;
for (k=49;k<n+49;++k)
if (map[k][j]>0)
++temp;
if (temp<max)
max=temp;
}
ans=0;
for (j=1;j<=max;++j)
{
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
memset(current,0,sizeof(current));
for (i=0;i<=49+n;++i)
for (k=0;k<=49+n;++k)
g[i][k]=map[i][k];
for (i=0;i<48;++i)
g[i][n+49]=j;
ISAP(48,n+49);
min=MAX;
for (i=0;i<48;++i)
if (f[i][n+49]<min)
min=f[i][n+49];
if (min>ans)
ans=min;
}
printf("%d\n",ans);
}
}
int main(void)
{
solve();
return 0;
}
注：1.感觉题目条件方面，没完全理解透，不知道其时间着手的核心思想。
2.我对时间的处理很简单，需要找到一个含有起点0:00和终点0:00的，存在就求其能工作时间之和，如果能大于24*60分钟，就等分配其工作，计数器加1。
3.不当之处希望和大家交流。算法这块需要深入呀！