首页 > ACM题库 > HDU-杭电 > HDU 4014-Jimmy’s travel plan[解题报告]HOJ
2015
04-15

HDU 4014-Jimmy’s travel plan[解题报告]HOJ

Jimmy’s travel plan

问题描述 :

Jimmy lives in a huge kingdom which contains lots of beautiful cities. He also loves traveling very much, and even would like to visit each city in the country. Jaddy, his secretary, is now helping him to plan the routes, however, Jaddy suddenly find that is quite a tough task because it is possible for Jimmy to ask route’s information toward any city. What was worth? Jaddy has to response for queries about the distance information nearly between any pair of cities due to the undeterminable starting city which Jimmy is living in when he raises a query. Because of the large scale of the whole country, Jaddy feel hopeless to archive such an impossible job, however, in order to gratify his manager, Jaddy is now looking forward to your assistance.
There might be good news about Jaddy’s work: since Jimmy is very lazy and would not like to travel to a destination whose distance between the original city is larger than TWO. That means only one intermediate city among the route is acceptable (Apparently, all the connecting paths between any two cities, if exists, have the same length as ONE). But don’t be fooled: Jimmy also needs to know that how many alternative different routes are available so that he can have more options. In particular two routes were named as different if and only if there is at least one path in the two routes is distinguishable, moreover, if more than one paths exist between a particular pair of cities, they are considered as distinct.

输入:

Input has multiple test cases. The first line of the input has a single integer T indication the number of test cases, then each test case following. For each test case, the first line contains two integers N and M indication the number of cities and paths in the country. Then M lines are following, each line contains a pair of integers A and B, separated by space, denoting an undirected path between city A and city B, all the cities are numbered from 1 to N. Then a new line contains a single integer Q, which means there are Q queries following. Each query contains a couple of integers A and B which means querying the distance and number of shortest routes between city A and B, each query occupy a single line separately.
All the test cases are separated by a single blank line.
You can assume that N, Q <= 100000, M <= 200000.

输出:

Input has multiple test cases. The first line of the input has a single integer T indication the number of test cases, then each test case following. For each test case, the first line contains two integers N and M indication the number of cities and paths in the country. Then M lines are following, each line contains a pair of integers A and B, separated by space, denoting an undirected path between city A and city B, all the cities are numbered from 1 to N. Then a new line contains a single integer Q, which means there are Q queries following. Each query contains a couple of integers A and B which means querying the distance and number of shortest routes between city A and B, each query occupy a single line separately.
All the test cases are separated by a single blank line.
You can assume that N, Q <= 100000, M <= 200000.

样例输入:

2
5 7
1 2
2 3
3 4
4 5
2 5
2 4
1 2
4
1 4
1 2
5 3
5 4

2 0
2
1 1
1 2

样例输出:

Case #1:
2 2
1 2
2 2
1 1
Case #2:
0 1
The pair of cities are not connected or too far away.

http://acm.hdu.edu.cn/showproblem.php?pid=4104

/*hdu4014Discount
给出N的数字 求不能由这个N个数字组合出的最小的数
思路:
首先思考:怎样给出N个数字 使可以组合出最多的连续的数字
1 2 4 8 16...2^n
联想 二进制 上面的数可以组合出1~2^(n+1)内的任何数
上面的情况已经是最稀疏的数字给出了,a1,a2..aM若密一些,则一定表示出sum[M]内的数字
归纳法:a[M+1]=m,则可以表示的数字 增加了[sum[M]+(m-sum[M)] , sum[M]+m],所以 m<=sum[M]+1;
*/
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1001
int a[MAXN],sum[MAXN];
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++)
            sum[i]=sum[i-1]+a[i];
        int i;
        for(i=1;i<=n;i++)
            if(a[i]>sum[i-1]+1)break;
        printf("%d\n",sum[i-1]+1);

    }
}

 

参考:http://www.cnblogs.com/sook/archive/2011/11/09/2242532.html


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;