Problem J 万神的数列
万神一天闲着无聊,在纸上写下了一个数列,包含 n 个整数 a 1 · · · a n ,并计
算出了它们的和
万神打乒乓球时,不慎弄丢了原来的数列。但是万神的脑子很好,因此他很
快回忆出了 S 的准确值,以及每个数字的大致范围,即第 k 个数字满足不等式
l k ≤ a k ≤ r k 。
万神希望恢复出原来的数列。但他正忙于华为软件精英挑战赛中的 NP 完
全问题,没功夫处理简单的 P 类问题,因此要求你帮他恢复原来的数列。若不存
在满足要求的数列,输出 “Xue Beng” (不含引号)。若有多个可能的数列,输
出字典序最小的。
字典序的定义见
http://www.cplusplus.com/reference/algorithm/lexicographical_compare/
输入格式
输入包含多组数据(至多 50 组),请处理到文件结束。
每组数据,第 1 行包含整数 n、S,用空格分割。
之后 n 行,第 i 行包含整数 l i 、r i 。用空格分割。
保证 1 ≤ n ≤ 10 5 ,0 ≤ l i ≤ r i ≤ 10 4 ,0 ≤ S ≤ 10 9 。
注意:本题输入文件较大(约 20MB),请使用较快的 I/O 方法以避免超时。
输出格式
对于每组数据输出 1 行。若存在满足要求的数列,输出其中字典序最小的
一个,数字之间用空格分割(行末不要有多余的空格)。否则,输出 “Xue Beng”
(不含引号)。
输入样例
3 6
1 5
1 4
1 3
1 2
0 1
输出样例
1 2 3
Xue Be
思路：
这题出的不错，，诶呀，诈一看，这数据深搜要超时么，然后怀着侥幸的心里写了一下深搜，然后就超时么．．．．．剪枝！，都剪成那啥怂样子了，，还超时，，打表，开不下数组，，完，卡了好久，，，最后灵机一动，，贪心！！！
每组数据，每个数列，，分为三部分:
(1)全部取最小(前半部分)
(2)枚举取哪一个(中间一个, 关键的一个)
(3)全部取最大(后半部分)
按这种贪心，必定保证符合题意
按字典序 -_- !，正常按字典序都是深搜啊～～
然后Wrong,，发现有个条件么判断好，两种情况无解，鄙人开始只考虑了一种，
(1) 全部取最大，依然比S小，必然无解
(2) 全部取最小，还比Ｓ大，必定无解
代码：
/*************************************************************************
> File Name: te.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年04月21日 星期四 22时51分56秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 1006;
int W[N], V[N];
int dp[N*50];
int main()
{
int n, w;
while(~scanf("%d%d", &n, &w))
{
int sum = 0;
for(int i=0; i<n; i++)
{
scanf("%d%d", &W[i], &V[i]);
sum += V[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i=0; i<n; i++)
for(int j=sum; j>=V[i]; j--)
dp[j] = min(dp[j-V[i]]+W[i], dp[j]);
for(int i=sum; i>=0; i--)
if(dp[i] <= w)
{
printf("%d\n", i);
break;
}
}
return 0;
}