【985系列】985的买饮料难题

左手的ㄟ右手 2022-09-25 06:23 97阅读 0赞

## Problem E: 985的买饮料难题 ##

Time Limit: 1 Sec Memory Limit:  128 MB  
Submit: 240 Solved: 128  
  
[Submit][] [Status][] [Web Board][]

## Description ##

天气太热了，985制定了对未来的规划即第i天喝a\[i\]瓶饮料。为了节约开支，他打听到了第i天每瓶饮料的价格p\[i\]。

为了不让自己的规划落空，他想知道这n天他至少要花多少钱。

精明的985可以选择在任意一天买数目不限的饮料，而且他有一个神奇的冰箱，可以将提前购买的饮料保存下来（至少在这n天里是可以饮用的）。

## Input ##

第一行输入一个整数t，代表有t组测试数据。

每组数据第一行输入一个整数n代表规划的总天数，接下来有n行，每行输入两个整数a\[\]，p\[\]分别代表上面提到的信息。

注：1 <= t <= 30，1 <= n <= 1000，1 <= a\[\]，p\[\] <= 100。

## Output ##

输出一个整数代表最后的结果。

## Sample Input ##

2
    2
    25 56
    94 17
    5
    39 21
    95 89
    73 90
    9 55
    85 32

## Sample Output ##

2998
    6321

## HINT ##

[Submit][] [Status][] [Web Board][]

#include<stdio.h> 
    #include<string.h> 
    #include<algorithm> 
    using namespace std; 
    const int N = 1000+10; 
    int a[N],p[N],vis[N]; 
    int main() { 
        int T; 
        scanf("%d",&T); 
        while(T--) { 
            int n,sum=0; 
            scanf("%d",&n); 
            for(int l=1; l<=n; l++) 
                scanf("%d%d",&a[l],&p[l]); 
            int flag=1,cnt; 
            cnt=p[1]; 
            vis[0]=1; 
            for(int l=2; l<=n; l++) { 
                if(p[l]<cnt) { 
                    cnt=p[l]; 
                    vis[flag]=l; 
                    flag++; 
                } 
            } 
            vis[flag]=n+1; 
            int t; 
            for(int l=0; l<flag; l++) { 
                t=vis[l]; 
                for(int j=t; j<vis[l+1]; j++) { 
                    sum=sum+p[t]*a[j]; 
                } 
            } 
            printf("%d\n",sum); 
        } 
        return 0; 
    } 
    /************************************************************** 
        Problem: 1896 
        Language: C++ 
        Result: Accepted 
        Time:7 ms 
        Memory:884 kb 
    ****************************************************************/

[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?cid=1157&pid=4&langmask=4093
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1896
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1896&cid=1157