题目168.房间安排问题
参考：https://blog.csdn.net/dxx_111/article/details/48093651
/*这一道题和杭电的4883的板凳真的是一道题,我感觉就是让求每一个单位时间段(时刻或者天)中所需要的板凳(或房间的个数),然后求所有时间段中所需要的房间(板凳)的最大值!虽然人家给的是时间段,但是你可以将它转化成时刻对应的房间的个数,然后求所需房间最多时刻所需的房间就是题中所求的所需房间的最小值! */#include#include #include using namespace std;int a,b,c;int t[300];int maxx;int main(){ int T; scanf("%d",&T); while(T--) { memset(t,0,sizeof(t));//初始化不敢丢！ maxx=0; int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); c+=b-1; for(int j=b;j<=c;j++) { t[j]+=a;//统计每天所需要的房间，求所有天数中的最大值！ maxx=(maxx>t[j])?maxx:t[j]; } } printf("%d\n",maxx); } return 0;}
自己错误的代码：
#include#include using namespace std;class plan{ public: int room; int begin; int end; void replan(int,int,int);}; void plan::replan(int r,int b,int e){ room = r; begin = b; end = e + b;}bool cmp(plan a,plan b){ return a.end < b.end;}int main(){ int T,N,r,b,e,sumroom; cin >> T; while(T--) { sumroom = 0; cin >> N; plan p[N]; for(int i = 0;i < N;i++) { cin >> r >> b >> e; p[i].replan(r,b,e); } sort(p,p+N,cmp); for(int i = 1;i < N;i++) cout << p[i].end << endl; sumroom += p[0].room; for(int i = 1;i < N;i++) { /* 9 12 */ if(p[i-1].end <= p[i].begin) /* 10 14 */ { /* 12 18 */ if(sumroom < p[i].room) sumroom = p[i].room; }else{ sumroom += p[i].room; } cout << sumroom << " "; } cout << sumroom << endl; }}
题目14.会场安排问题
区间贪心问题：
结束的时间越早，留给后面安排节目的时间就越长。 所以，先对结束时间排序，将时间短的放在前面，然后进行循环比较，其之后的活动开始时间晚于此次时间短的，即可成功加入一个活动。
#include#include using namespace std;struct meeting{ int startTime; int endTime;}; bool cmp(meeting a,meeting b){ return a.endTime < b.endTime;}int main(){ int n,m,i,j,k,above; cin >> n; int times[n]; for(i = 0;i < n;i++) { cin >> m; meeting meet[m]; times[i] = 1; above = 0; for(j = 0;j < m;j++) cin >> meet[j].startTime >> meet[j].endTime; //获得输入 sort(meet,meet + m,cmp); for(j = 1;j < m;j++) { if( (meet[above].endTime + 1) <= meet[j].startTime ) { times[i] += 1; above = j; } } } for(i = 0;i < n;i++) cout << times[i] << endl; return 0; }
做笔记主要用来反思二者的差别。。。。。