SP348 EXPEDI - Expedition

1
4
4 4
5 2
11 5
15 10
25 10

2

以下来自《挑战程序设计竞赛》


以及我的辣鸡程序（竟然没超时！）

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"# "<<x<<" "<<endl;
typedef long long ll;
const ll mod=2147483647;
const ll N=1e4+7;
ll n,L,P,m,a[N],b[N],ans,t;
bool val[N];
void solve()
{
    ll now=0;ans=0;
    memset(val,1,sizeof val);
    priority_queue<ll>q;
    while(now<L)
    {
        now+=P;
        if(now>=L)break;
        P=0;
        for(int i=1;i<=n;i++)
        {
            if(L-a[i]<=now&&val[i])
                q.push(b[i]),val[i]=0;
        }
        if(q.empty())
        {
            cout<<"-1"<<endl;
            return ;
        }
        P+=q.top();
        q.pop();
        ans++;
    }
    cout<<ans<<endl;
    return ;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i]>>b[i];
        cin>>L>>P;
        solve();
    }
    return 0;
}