本文主要是介绍HNU 12988 It Can Be Arranged，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HNU 12988 It Can Be Arranged
http://acm.hnu.cn/online/?action=problem&type=show&id=12988&courseid=0
n个课程 每个教室的容量是m个人 给出n个课程的开始和结束时间 以及上课的人数
给出n*n的矩阵 a（i,j）表示第i个课程之后 如果j课程也要使用该教室 就要花这么多的时间去打扫教室
求需要安排的最少的教室
第一感觉是跟在hdu上做的一题差不多 那个是餐厅来顾客吃饭 安排桌子的问题
写了一半感觉不对 因为第i个课程结束之后不知道要选取哪个课程的打扫时间
后来发现有人过了 就觉得应该是暴力过的 就试着 往后写了 后来就过了。。
总的来说还是觉得这题有点问题的 也许是数据太水了。。。没有给出想到的那种情况的数据
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 100100#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOV(i,a,b) for(int i=a;i>=b;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define MEM(a,x) memset(a,x,sizeof a)
#define ll __int64using namespace std;struct st
{int ti;int num;int order;int ct[110];//打扫时间bool operator <(const st p)const{return ti>p.ti;}
};//开始时间
st s[110];struct ft
{int ti;int num;int order;bool operator <(const ft p)const{return ti>p.ti;}
};//结束时间
ft f[110];priority_queue<st> q;
priority_queue<ft> p;int main()
{
//freopen("ceshi.txt","r",stdin);int tc;scanf("%d",&tc);int cs=1;while(tc--){int n,m;scanf("%d%d",&n,&m);int cnt=1;for(int i=1;i<=n;i++){int a,b,ss;scanf("%d%d%d",&a,&b,&ss);s[cnt].ti=a; s[cnt].num=ss; s[cnt].order=i;f[cnt].ti=b; f[cnt].num=-ss;f[cnt].order=i;p.push(f[cnt]);cnt++;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){
// if(i==j) continue;int x;scanf("%d",&x);s[i].ct[j]=x;}q.push(s[i]);}st xx; ft yy;int mx=-1;int z=0;while(!q.empty()){xx=q.top();yy=p.top();int start=xx.ti;int finish=yy.ti;int k=xx.order;
// cout<<"yy.order "<<yy.order<<endl;
// cout<<"kk "<<k<<endl;
// cout<<"s.ct[k]"<<s[yy.order].ct[k]<<" finish yy.order "<<finish<<" "<<yy.order<<endl;
// cout<<"start "<<start<<endl;if((s[yy.order].ct[k]+finish)<start){
// cout<<"zzzz"<<z<<endl;z+=(yy.num)/m;if(yy.num%m) z++;p.pop();
// cout<<"1111zzzz"<<z<<endl;
// cout<<"num "<<yy.num<<endl;}else{z+=(xx.num)/m;if(xx.num%m) z++;q.pop();
// cout<<"2222zzzz"<<z<<endl;
// cout<<"num "<<xx.num<<endl;}mx=max(mx,z);}while(!p.empty()) p.pop();printf("Case %d: %d\n",cs++,mx);}return 0;
}
这篇关于HNU 12988 It Can Be Arranged的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
