hdu6011LotusandCharacters思路及题解

Problem Description

Lotus has n kinds of characters,each kind of characters has a value and a amount.She wants to construct a string using some of these characters.Define the value of a string is:its first character’s value*1&＃43;its second character’s value *2&＃43;…She wants to calculate the maximum value of string she can construct.
Since it’s valid to construct an empty string,the answer is always ≥0。

Input

First line is T(0≤T≤1000) denoting the number of test cases.
For each test case,first line is an integer n(1≤n≤26),followed by n lines each containing 2 integers vali,cnti(|vali|,cnti≤100),denoting the value and the amount of the ith character.

Output

For each test case.output one line containing a single integer,denoting the answer.

Sample Input

2
2
5 1
6 2
3
-5 3
2 1
1 1

Sample Output

35
5


思路

这道题的话&＃xff0c;他是要用字符构建字符串实现最大值&＃xff0c;每个字符有不同的价值和个数&＃xff0c;每个字符的价值在不同的位数乘以对应的值。
我的思路&＃xff1a;首先想到把价值从大到小排列&＃xff0c;因为最大的价值肯定是要放在最后一位的&＃xff0c;这样实现价值最大化。每个字符的排列&＃xff0c;肯定是从小到大排列的&＃xff0c;这样才能保证最大值。但是这样的话&＃xff0c;需要注意一个问题&＃xff0c;当负数足够小的时候&＃xff0c;他放在前面&＃xff0c;反而整个字符串的价值会变大。基于这个观点&＃xff0c;可以进行观察&＃xff0c;当把一位负数放在首位的话&＃xff0c;后面的数都向后移了一位&＃xff0c;也就是说&＃xff0c;之前再字符串每个字符的权值都变大了1。举个例子&＃xff0c;-1 2 2 和 2 2&＃xff0c;前面是-1&＃43;4&＃43;6&＃xff0c;后面是2&＃43;4 。2 2的这个区间扩大了2&＃43;2&＃xff0c;因此的话&＃xff0c;可以用一个很简便的方法(最开始我是想到枚举的&＃xff0c;发现有点烦琐)。用一个变量border记录当前所有数字的和&＃xff0c;当他小于0的时候&＃xff0c;则说明这个时候负数已经过大&＃xff0c;不能再加负数进来了。例如-2 -1 1 2 这样的话&＃xff0c;刚好是相加为0&＃xff0c;他的值也和1 2字符串相等。接着&＃xff0c;代码就可以写完了…

代码

#include
#include
using namespace std;
const int maxn &＃61; 1001;
struct node
{int value; // 字母价值int num; //字母个数
};
bool cmp(node n1,node n2)
{return n1.value > n2.value;
}
int main()
{int t;cin >> t;int n, max_value;while (t--){cin >> n;max_value &＃61; 0;node nodes[maxn];for (int i &＃61; 0; i < n; &＃43;&＃43;i){cin >> nodes[i].value >> nodes[i].num;}//border代表临界条件int border&＃61;0;sort(nodes, nodes &＃43; n, cmp);for (int i &＃61; 0; i <n;&＃43;&＃43;i){for (int j &＃61; 0; j < nodes[i].num; &＃43;&＃43;j){//代码优化后&＃xff0c;最初用的是枚举法&＃xff0c;依次进行判断border &＃61; border &＃43; nodes[i].value;//如果小于0&＃xff0c;则说明这个负数过大&＃xff0c;之后的负数也不考虑if (border < 0)break;max_value &＃61; border &＃43; max_value;}}cout << max_value << endl;}return 0;
}