HDU 5477 A Sweet Journey

A Sweet Journey

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

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)

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: L

i

,R

i

, which represents the interval [L

i

,R

i

]

is swamp.

1≤n≤100,1≤L≤10

5

,1≤A≤10,1≤B≤10，1≤L

i

<R

i

≤L

.

Make sure intervals are not overlapped which means R

i

<L

i+1

for each i ( 1≤i<n

).

Others are all flats except the swamps.

Output For each text case:

Please output “Case #k: answer”(without quotes) one line, where k means the case number counting from 1, and the answer is his minimum strengths in the beginning.

Sample Input

1
2 2 2 5
1 2
3 4
        

Sample Output

Case #1: 0
        

Source 2015 ACM/ICPC Asia Regional Shanghai Online 

題意：一個人騎自行車旅行，路的長度為L，陸地上每裡獲得b點力量，沼澤中每裡失去a點力量，n為沼澤的數量，下面的nz組資料代表沼澤的起點和終點。 沼澤的順序都是從起點到終點的，不用考慮順序。簡單模拟接可以了。

AC代碼：

#include <cstdio>
#include <algorithm>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
    int t,a,b,l,n;
    int kase=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&a,&b,&l);
        int sum=0;
        int last=0;
        int maxn=INF;
        while(n--)
        {
            int start,end;
            scanf("%d%d",&start,&end);
            sum+=(b*(start-last)-a*(end-start));
            maxn=min(maxn,sum);
            last=end;
        }
        printf("Case #%d: ",++kase);
        if(maxn<0)
            printf("%d\n",-maxn);
        else
            printf("0\n");
    }
    return 0;
}
           

水模拟：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool a[100000+5];
int main()
{
    int n,A,B,L;
    int kase=0;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>A>>B>>L;
        memset(a,true,sizeof(a));
        while(n--)
        {
            int x,y;
            cin>>x>>y;
            for(int i=x+1; i<=y; i++)
                a[i]=false;
        }
        int ans=0;
        int minn=0;
        for(int i=1; i<=L; i++)
        {
            if(a[i])
                ans+=B;
            else
                ans-=A;
            if(ans<0)
            {
                minn=min(minn,ans);
            }
        }
        cout<<"Case #"<<++kase<<": ";
        if(minn<0)
            cout<<-minn<<endl;
        else
            cout<<"0"<<endl;
    }
return 0;
}