首页 > ACM题库 > HDU-杭电 > HDU 4546-比赛难度-优先队列-[解题报告]HOJ
2015
07-25

HDU 4546-比赛难度-优先队列-[解题报告]HOJ

比赛难度

问题描述 :

  最近,小明出了一些ACM编程题,决定在HDOJ举行一场公开赛。
  假设题目的数量一共是n道,这些题目的难度被评级为一个不超过1000的非负整数,并且一场比赛至少需要一个题,而这场比赛的难度,就是所有题目的难度之和,同时,我们认为一场比赛与本场题目的顺序无关,而且题目也不会重复。
  显而易见,很容易得到如下信息:
  假设比赛只用1个题目,有n种方案;
  假设比赛使用2个题目,有(n-1)*n/2种方案;
  假设比赛使用3个题目,有(n-2)*(n-1)*n/6种方案;
  …………
  假设比赛使用全部的n个题目,此时方案只有1种。
  
  经过简单估算,小明发现总方案数几乎是一个天文数字!
  为了简化问题,现在小明只想知道在所有的方案里面第m小的方案,它的比赛难度是多少呢?

输入:

输入数据的第一行为一个整数T(1 <= T <= 20),表示有T组测试数据。
每组测试数据第一行为两个整数n, m(0 < n, m <= 10000),表示现在有n个题目,现在要求第m小的方案的比赛难度。接下来第二行有n个数字,分别表示这n个题目的难度值。

输出:

输入数据的第一行为一个整数T(1 <= T <= 20),表示有T组测试数据。
每组测试数据第一行为两个整数n, m(0 < n, m <= 10000),表示现在有n个题目,现在要求第m小的方案的比赛难度。接下来第二行有n个数字,分别表示这n个题目的难度值。

样例输入:

2
5 6
1 1 1 1 1
5 25
1 2 3 4 5

样例输出:

Case #1: 2
Case #2: 11

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=4546

题意:给你n个数,问这n个数的组合的和,第m小是多少

分析:很明显的,要给初始序列排序(我写的时候居然忘记排序了,看来下次得把步骤写下来= =),然后发挥想像力,你会发现这其中有一定规律,我们可以假设有这样的元素,

struct  data

{

    int start, i;

}

序列为a[ i ],start表示当前的组合的和,i表示下次添加的元素为a[ i ];

将这些元素加入优先队列

一开始只有 a.start=0, a. i=0的元素,肯定是选择他,将他取出,然后得到两个元素,b.start=a.start, b.i=a.i+1,     c.start=a.start+a[i], c.start=i+1

这个也就是说将组合的最后一个元素往后移,得到一个新组合,或者把当前组合作为一个新的开头,也就是组合个数多加一个,并且最后一个元素大于前面的元素

这样能保证每次弹出的元素是最小的,并保证生成的元素不会重复,所以问题得到解决

将得不是很清楚,看看代码就明白了

代码:

/** head files*/
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;

/** some operate*/
#define PB push_back
#define MP make_pair
#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
#define MSET(arr,val) memset(arr,val,sizeof(arr))
#define MAX3(a,b,c) max(a,max(b,c))
#define MAX4(a,b,c,d) max(max(a,b),max(c,d))
#define MIN3(a,b,c) min(a,min(b,c))
#define MIN4(a,b,c,d) min(min(a,b),min(c,d))

/** some const*/
#define N 222222
#define M 222222
#define PI acos(-1.0)
#define oo 1111111111

/** some alias*/
typedef long long ll;



/** some template names, just push ctrl+j to get it in*/
//manacher
int a[N];
typedef struct data
{
	int start,i;
	data():start(0),i(0){}
	data(int a, int b):start(a),i(b){}
}way;
struct cmp
{
    bool operator()(const data &x, const data &y)
	{
	    return x.start+a[x.i]>y.start+a[y.i];
	}
};
priority_queue< way, vector<way> , cmp > pq;
int main()
{
    int i,n,m,t,ans,cs=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<n;++i)
            scanf("%d",&a[i]);
        sort(a,a+n);
        while(!pq.empty())pq.pop();
        pq.push(data(0,0));
        ans=0;
        while(m--)
        {
            if(pq.empty())continue;
            way tmp=pq.top();
            ans=tmp.start+a[tmp.i++];
            pq.pop();
            if(tmp.i<n)
            {
                pq.push(tmp);
                tmp.start=ans;
                pq.push(tmp);
            }
        }
        printf("Case #%d: %d\n",++cs,ans);
    }
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/fp_hzq/article/details/8942842