2015 ACM/ICPC Asia Regional Shanghai Online 1010题

雨点打透心脏的1/2处 2022-08-08 19:58 124阅读 0赞

\[题目链接\]  
([http://acm.hdu.edu.cn/contests/contest\_showproblem.php?pid=1010&cid=623][http_acm.hdu.edu.cn_contests_contest_showproblem.php_pid_1010_cid_623])  
题目描述：  
A Sweet Journey

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 2619 Accepted Submission(s): 1007

Problem Description  
Master Di plans to take his girlfriend for a travel by bike. Their journey, which can be seen as a line segment of length L, is a road of swamps and flats. In the swamp, it takes A point strengths per meter for Master Di to ride; In the flats, Master Di will regain B point strengths per meter when riding. Master Di wonders：In the beginning, he needs to prepare how much minimum strengths. (Except riding all the time,Master Di has no other choice)  
![这里写图片描述][C623-1010-1.jpg]

Input  
In the first line there is an integer t (1≤t≤50), indicating the number of test cases.  
For each test case:  
The first line contains four integers, n, A, B, L.  
Next n lines, each line contains two integers: Li,Ri, which represents the interval \[Li,Ri\] is swamp.  
1≤n≤100,1≤L≤105,1≤A≤10,1≤B≤10，1≤Li

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    bool flag[100010];
    
    int main()
    {
        int T,n,a,b,R;
        int l,r;
        cin>>T;
        int k=1;
        while(T--)
        {
            scanf("%d%d%d%d",&n,&a,&b,&R);
            memset(flag,false,sizeof(flag));
            while(n--)
            {
                scanf("%d%d",&l,&r);
                for(int i=l;i<=r-1;i++)
                {
                    flag[i]=true;
                }
            }
            int ans,min;
            ans=0;
            min=0xfffffff;
            for(int  i=0;i<R;i++)
            {
                if(flag[i]==false)
                {
                    ans+=b;
                }
                else if(flag[i]==true)
                {
                    ans-=a;
                }
                if(ans<min)
                {
                    min=ans;
                }
            }
            if(min>=0)
            printf("Case #%d: 0\n",k++);//特别注意，min>=0时，输出0即可
            else
            {
                printf("Case #%d: %d\n",k++,-min);
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_contests_contest_showproblem.php_pid_1010_cid_623]: http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&cid=623
[C623-1010-1.jpg]: /images/20220731/9da15b3190e047748d52a92b039307d5.png