题目链接：http://codeforces.com/problemset/problem/349/B
题目意思：给定v升的颜料和9个需要花费ad 升的颜料，花费ad 升的颜料意味着得到第d个数字，现在要求在所有的花费不超过v升的情况下，使得这些数字组合起来是最大的。
一开始直接从最小花费的颜料着手，如果花费的颜料是相同的，就转到从d（也就是位数）最大贪心。这样测试9就开始卡住了。
受到乌冬兄的指点迷津，终于有了思路，陆陆续续改了很多次，终于过了。以下摘自他的语录，白话文，大家请谅解：
稳用颜料最少，最大的数字，先保证位数最长，然后再将剩余颜料从大数字开始贪心
因为要数最大，所以根据“数”的比较顺序：
1。比较位数
2。从高位开始比较
从数字比较的方法，推出贪心既思路
由于本人悟性太低，下面是更详细的解说：
1、先稳到用最小颜料既数字d，假设它价值为c
2、先构造出s = v div c个d，求出剩余颜料r = v mod c
3、从最高位扫描s，从大到小枚举可替换数字d' >= d，假设价值为c'：若c'-c <= r，则替换当前位置的d为d'， r -= c' - c
4、最后得出替换后的s, s'即为所求
注意：价值即一个数字要使用的颜料量
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = 1e6 + ;
struct paint
{
int index; // 数字
int num; // 该数字所花费的颜料量
} a[maxn], b[maxn]; int s[maxn]; // 用于保存结果 int cmp(paint a, paint b)
{
if (a.num != b.num) // 先保证用的颜料量最少
return a.num < b.num;
return a.index > b.index; // 再保证数字最大
} int main()
{
int i, j, v, tmp, t1;
while (scanf("%d", &v) != EOF)
{
// freopen("in.txt", "r", stdin);
for (i = ; i <= ; i++)
{
a[i].index = i;
scanf("%d", &a[i].num);
b[i].index = i; //b用于保存未排序前的序列，以便下面从大数字开始枚举
b[i].num = a[i].num;
}
sort(a+, a+, cmp);
if (v < a[].num) // v比最少花费的颜料更少
printf("-1\n");
else
{
tmp = v / a[].num; // 得出最大位数
if (v % a[].num == ) // 如果刚好可以除尽，最大的数就是tmp个a[1].num的数。
{
for (i = ; i < tmp; i++)
printf("%d", a[].index);
printf("\n");
}
else
{
for (i = ; i < tmp; i++)
{
s[i] = a[].index; // 先得出目前来说最长的数字，但可能不是最终结果
}
int r = v % a[].num; // 余数
t1 = r;
for (i = ; i < tmp; i++)
{
for (j = ; j >= ; j--) // 从最大的位数开始枚举
{
if (b[j].num - a[].num <= r && a[].index < b[j].index) // 没有超过余数且数字比原来的排列数字的位数要大
{
s[i] = b[j].index;
r = r - (b[j].num - a[].num); // 余数要有所减少
break;
}
}
}
if (t1 == r) // 如果根本没有可替换的数，那么就和刚好除尽的是同一种情况
{
for (i = ; i < tmp; i++)
printf("%d", a[].index);
printf("\n");
}
else
{
for (i = ; i < tmp; i++) // 否则有替换的就输出新的最大数字
{
printf("%d", s[i]);
}
printf("\n");
}
}
}
}
return ;
}