现在的位置: 首页 > 综合 > 正文

hdoj 1050 Moving Tables

2018年01月21日 ⁄ 综合 ⁄ 共 927字 ⁄ 字号 评论关闭

从教程上看到是用贪心的思想求解, 但是自己途中还不求错了。

原因是两排,每两个房间只对应一个过道。然后我们对过道计数即可。

贪心的想法就是每次我选重叠最多的过道进行搬。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<cstring>
#include<cmath>
#include<fstream>
typedef long long ll;
#define cl(a,n) memset(a,n,sizeof a )
using namespace std;
/****************************
       By:七柳先森丶
       Date: 1.4 2015
*****************************/
const int mx=210;
//贪心,贪心策略为每次只选交叉最多的边交集。。 
int  gd[mx];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
		int N;
		for(int j=0;j<200;j++) gd[j]=0;
		scanf("%d",&N);
		int a,b,min1=-1;
		for(int i=1;i<=N;i++){
			scanf("%d%d",&a,&b);
			//比较坑的一点,a有可能比b大。 
			//还有就是除以2,二排房子,一个走道,对面的可以直接搬。。
			//对面的点只算一个点。 
			//只计算一个过道被点用的次数。
			//如果用房间代表过道,则有可能不会有重叠。 
			int begin=(a-1)/2;
			int end=(b-1)/2;
			if(begin > end) swap(begin,end); 
			for(int i1=begin;i1<=end;i1++)
				gd[i1]++; 
		}
		for(int i=0;i<200;i++){
			if(gd[i]>min1) min1=gd[i];
		}
		printf("%d\n",min1*10);
	}
	//system("pause");
    return 0;
}

抱歉!评论已关闭.