比赛难度
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 817 Accepted Submission(s): 296
假设题目的数量一共是n道，这些题目的难度被评级为一个不超过1000的非负整数，并且一场比赛至少需要一个题，而这场比赛的难度，就是所有题目的难度之和，同时，我们认为一场比赛与本场题目的顺序无关，而且题目也不会重复。
显而易见，很容易得到如下信息：
假设比赛只用1个题目，有n种方案；
假设比赛使用2个题目，有(n-1)*n/2种方案；
假设比赛使用3个题目，有(n-2)*(n-1)*n/6种方案；
............
假设比赛使用全部的n个题目，此时方案只有1种。
经过简单估算，小明发现总方案数几乎是一个天文数字！
为了简化问题，现在小明只想知道在所有的方案里面第m小的方案，它的比赛难度是多少呢？
每组测试数据第一行为两个整数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
解题目报告
题目大意：
有N个包含难度值的题目，每次比赛可以选若干个不同题目，则有C(N,1)+C(N,2)+...+C(N,N)种可能的题目组合的方案，每个方案的题目难度的总和则称为比赛难度。让你输出第M小的方案的比赛难度。
思路：
如果只是考虑去计算所以方案的比赛方案的话，0<N<=10000,方案数有C(N,1)+C(N,2)+...+C(N,N)，不可能枚举所以的方案数再去求第M小的方案的比赛难度。
不过,M的范围是限制在（0,10000]之间，也就是这题的突破口在在于直接求解第M小的数即可，也就是每次取出最小的那个方案的比赛难度，取M次即可、
假如我们有N个题目，题目难度分别为X1,X2,X3...XN(Xi<=XJ,i<j)。
我们可以很容易知道，比赛方案最小的比赛难度为X1，
同样，也可以知道，比赛方案第二小的比赛难度为X2，
如果继续求解第三小的比赛难度，那第三小的是X1+X2,还是X3呢，
如果，第三小的是X3，那么第四小的是X1+X2，还是X4呢。
如果，第三小的是X1+X2,那么第四小的是X1+X3，还是X3呢？
对于求最小值或者最大值的问题，我们可以用优先队列来求解，但如何求解也在于你如何构造一个合理的结构体来实现、
首先，我们要构造的这个结构体，肯定是要来记录某一个方案的比赛难度的总和、
然后，我们可以确定的是第一小的方案的比赛难度，但是如何实现记录每一个方案的比赛难度呢？
我们先把所有题目的比赛的难度都先排好序，从小到大依次拿题目，便能保证你下一个方案的比赛难度是递增的。
我们保证，第一次拿出来的结构体（方案）是最小的，然后在第一次那结构体（方案）的基础上，放入比它大的其他方案（结构体），这样，每次同样的操作，便可以实现在第M次拿出第M小的方案的比赛难度。
我们要实现每个方案前后是有关联的，也就是说我们需要构建的结构体也是需要能够关联到前后方案的。
我们在结构体里面，定义一个Sum，用来记录之前方案的比赛难度的总和。（前关联）
然后在定义一个ID，则是表示当前加入的方案的题目难度。（后关联）
每一个结构体表示的方案的比赛难度则是=Sum+Num[ID];
struct Node
{ //每一个结构体表示一种题目难度总和=Sum+Num[ID];
int Sum;//记录之前题目难度的总和，
int ID;//记录下一个题目的难度
friend bool operator <(Node a,Node b){
return a.Sum+Num[a.ID]>b.Sum+Num[b.ID];
}//把题目难度总和比较小的优先
};
需要构建的合理的结构体
构建完结构体，还有很重要的一点是，如何正确放入下一个方案？
我们可以知道，对于当前方案的话，比赛的难度为Sum+Num[ID],那么，比他大的方案有也就只有Sum+Num[ID+1]。（更新下标值）
而且，你还需要更新下一个方案的比赛难度的总和，也就是(Sum+Num[ID])+Num[ID+1]。（更新方案的比赛难度总和）
用优先队列维护最小值，每次取出最小值在进行更新便可以得出第M小的方案的比赛难度、
PS：对放入(Sum+Num[ID])+Num[ID+1]还是不太理解的话，可以想想，虽然Sum+Num[ID+1]肯定小于(Sum+Num[ID])+Num[ID+1],
但你无法确定，你的下下一个方案也就是Sum+Num[ID+1]+Num[ID+2]是否会比(Sum+Num[ID])+Num[ID+1]小?
这样， 也才能够把所有方案从小到大都放入优先队列中，在不懂的就自己去画画图就大概知道为什么了、
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int Num[];//Num[i],记录第i个题目的难度
struct Node
{ //每一个结构体表示一种题目难度总和=Sum+Num[ID];
int Sum;//记录之前题目难度的总和，
int ID;//记录下一个题目的难度
friend bool operator <(Node a,Node b){
return a.Sum+Num[a.ID]>b.Sum+Num[b.ID];
}//把题目难度总和比较小的优先
};
int main()
{
int T,N,M,i,t=;
Node TMD;
scanf("%d",&T);
while(T--){
priority_queue<Node>q;
scanf("%d%d",&N,&M);
for(i=;i<N;i++){
scanf("%d",&Num[i]);
}
sort(Num,Num+N);//将题目难度小的排在前面
TMD.Sum=;//初始状态，题目难度为0
TMD.ID=;//默认从最小的开始
q.push(TMD);
printf("Case #%d: ",t++);
while(M--){
TMD=q.top();q.pop();
if(M==){//输出第M小的题目难度总和
printf("%d\n",TMD.Sum+Num[TMD.ID]);
}
if(++TMD.ID<N){
q.push(TMD);//更新的下标值的
TMD.Sum+=Num[TMD.ID-];
q.push(TMD);//更新下标值以及总和
}
}
}
return ;
}