1355选择旅馆.doc

选择客栈【NOIP2011提高组Day1】 Time Limit:10000MS? Memory Limit:128000KTotal Submit:1 Accepted:1 Description 选择客栈(hotel.cpp/c/pas) 【问题描述】 　　丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从1 到n 编号。每家客栈都按照某一种色调进行装饰（总共k 种，用整数0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。 　　两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。 　　他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。 Input 输入文件 hotel.in，共n+1 行。 　　第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值； 　　接下来的 n 行，第i+1 行两个整数，之间用一个空格隔开，分别表示i 号客栈的装饰色调和i 号客栈的咖啡店的最低消费。 Output 输出文件名为 hotel.out。 　　输出只有一行，一个整数，表示可选的住宿方案的总数。 Sample Input 5 2 3 0 5 1 3 0 2 1 4 1 5 Sample Output 3 Hint 【输入输出样例说明】  　　2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，但是若选择住4、5 号客栈的话，4、5 号客栈之间的咖啡店的最低消费是4，而两人能承受的最低消费是3 元，所以不满足要求。因此只有前3 种方案可选。 【数据范围】 对于 30%的数据，有n≤100； 对于 50%的数据，有n≤1,000； 对于 100%的数据，有2≤n≤200,000，0 Source NOIP2011Day1 NO.2 解法： 对于这道题，刚开始我想到的是用组合数学的乘法原理，后来没想到方法，就把思路放在了二分查找上，拿了满分，时间也用时比较短，只有约0.5s。对于这个结果，我还是比较满意的。在此稍微讲一讲思路吧：记 sum_color[i]表示i色调的个数。?? num[i][j]为i色调第j个旅馆的编号。?? near[i]为最接近i旅馆的、最小消费小于p的咖啡店所在旅馆编号。?? c[i]为i旅馆的色调。?? 首先，i从1-n枚举每一个旅馆，表示两人所在旅馆中编号靠后的那一个。通过二分查找可以在log2c[i]的时间内求出i旅馆在num[c[i]]中所在的位置，在通过二分查找找到num[c[i]]数组中编号最大且编号小于near[i]的旅馆的编号，计为l，显然l以前的每一个旅馆都可以和i旅馆搭配，只要sum+=l；这道题用了我近1个半个小时，比完之后发现我大材小用了——完全可以用O(NK)的方法。 听说还有O(N)的做法，本人水平不够，完全没这个能力，请大家参考神犇们的博客吧。 程序1： #includestdio.h#includestdlib.hlong long ans;int left,right,middle,n,color,max,i,j,sum_color[60],num_color[60][200010],near[200010],c[200010],p;int main(){??? scanf(%d %d %d,n,color,max);??? for(i=1;i=n;i++)??? {??????? scanf(%d %d,c[i],p);??????? num_color[c[i]][++sum_color[c[i]]]=i;??????? near[i]=near[i-1];??????? if(p=max)??????????? near[i]=i;??? }??? for(i=2;i=n;i++)??? {??????? int num=c[i],num1=near[i];??????? if(!num1)??????????? continue;??????? left=1,right=sum_color[num];??????? while(1)??????? {??????????? middle=(left+right)1;??????????? if(num_color[num][middle]i)??????????????? left=mi