Lotus has nn 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+its second character’s value *2+…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。
First line is T(0≤T≤1000)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.
For each test case.output one line containing a single integer,denoting the answer.
2 2 5 1 6 2 3 -5 3 2 1 1 1 3 -1 3 2 1 1 1 2 -1 5 4 2
35 5 8 37
题意：用字母构建字符串实现最大值。给出字符的价值和个数，字符顺序按x1，x2，x3依次递增。 想法：把价值从大到小排列，从大到小取，外层循环有几行数即几个不同的价值，内层循环同一价值个数，若是相同就累加。 不要不管负数，如果负数的值很小,而数的总数增加一位,那么整体数的和也可能增加。 ↑先把所有的加起来如果结果小于0，就把这个负数去掉。不然不能随便去掉这个负数。
官方题解： 根据排序不等式，显然应该把字母从小往大放。 一种错误的做法是把正权值的字母取出来从前往后放。 错误是因为负权的也可能出现在答案中：放在最前面来使后面每个字母的贡献都增加。 正确的做法是把字母从大往小从后往前放，如果加入该字母后答案变劣就停下来。 由于从后往前放我们没法确定位数,所以我们还是排序后从前往后放,最后更新一下最大值即可; 处理方法: 我们先假设全部的字母全部用上,然后依次减少负数,每少一个负数相应的每一个字母的权值都会减少1,我们这里就用sum1来记录这个和,并更新最大值
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;pair<int,int>p[30];//类型之间定义都是用,隔开int main(){ int t,i,j,a,b,n; ll sum1,sum; cin>>t; while(t--) { cin>>n; sum=0; sum1=0; for(i=0; i<n; ++i) { cin>>a>>b; p[i]=make_pair(a,b); } sort(p,p+n);//默认对pair的fisrt排序 for(i=n-1; i>=0;--i) //按权值从大到小用啊 { for(j=0; j<p[i].second; ++j) {//同一价值下的累加 sum1+=p[i].first; if(sum1<0)break; sum+=sum1; } } cout<<sum<<"/n"; } return 0;}然鹅官方的实在是太官方了，找到了一个民间版本XD民间讲解版本
新闻热点
疑难解答
