Lotus and Characters

骑猪看日落 2022-07-11 08:44 194阅读 0赞

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 262144/131072 K (Java/Others)

Problem Description

Lotus has nnn 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\\geq 0≥0。

Input

First line is T(0≤T≤1000)T(0 \\leq T \\leq 1000)T(0≤T≤1000) denoting the number of test cases. For each test case,first line is an integer  n(1≤n≤26)n(1 \\leq n \\leq 26)n(1≤n≤26),followed by nnn lines each containing 2 integers vali,cnti(∣vali∣,cnti≤100)val\_i,cnt\_i(|val\_i|,cnt\_i\\leq 100)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

#include<stdio.h>
    struct node
    {
        int p;
        int c;
    }a[27],m;
    int dele (int n)
    {
        int i,j;
        for(i=0;i<n;i++)
        {
            if(a[i].p<=0)
            {
                for(j=i;j<n;j++)
                {
                    a[j]=a[j+1];
                }
                n--;
            }
        }
        return n;
    }
    void qsort (int left, int right)
    {
        int i=left;
        int j=right;
        int mid=a[i].p;
        m=a[i];
        if(i>=j)
            return ;
        while(i<j)
        {
            while(i<j&&a[j].p>=mid)
                j--;
            a[i]=a[j];
            while(i<j&&a[i].p<=mid)
                i++;
            a[j]=a[i];
        }
        a[i]=m;
        qsort(left,i-1);
        qsort(j+1,right);
    }
    int main()
    {
        int t,n,i,j;
        int max;
        int count;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                scanf("%d%d",&a[i].p,&a[i].c);
            }
            n=dele(n);
            qsort(0,n-1);
            max=count=0;
            for(i=0;i<n;i++)
            {
                for(j=0;j<a[i].c;j++)
                {
                    count++;
                    max+=a[i].p*count;
                }
            }
            printf("%d\n",max);
        }
        return 0;
    }