题解 UVA11034 【Ferry Loading IV】

· · 题解

题目大意：

有n辆车要过河，有一个长度为c\times 100长度的船，船一开始在左岸，已知左岸与右岸车来的顺序，求最少运几次可以将车全部运完。

题解：

因为车的顺序固定，因此用贪心策略，每次尽量运多的车。

如果当前船还可以放车就继续放，不然就换下一次。这样分别对左岸与右岸进行贪心操作。

得到左岸的车全部到右岸的次数ans1，右岸的车全部到左岸的次数ans2。

那么由于船左右开，且一开始在左岸，尽量要使船开的次数少，因此ans1=ans2或者ans1=ans2+1。贪心即可。

#include<bits/stdc++.h>
using namespace std;
int ans[2],s,n,s1[2],x,_;
string st;
int main(){
    cin>>_;
    while(_--){
        ans[0]=ans[1]=0;//代表次数
        s1[1]=s1[0]=0;//当前船剩余的长度
        cin>>s>>n;
        s*=100;//读入船的长度是米，车的长度是厘米
        for(int i=1;i<=n;i++){
            int y;
            cin>>x>>st;
            if(st=="left")y=1;//左边是0，右边是1，分开处理
            else y=0;
            if(s1[y]+x<s)s1[y]+=x;//尽量运多的车
            else ans[y]++,s1[y]=x;
        }
        if(s1[1])ans[1]++;
        if(s1[0])ans[0]++;
        if(ans[0]<ans[1]-1)ans[0]=ans[1]-1;//求次数
        if(ans[1]<ans[0])ans[1]=ans[0];
        cout<<ans[0]+ans[1]<<endl;//最后的答案就是两种次数之和
    }
}