题意:n辆车,低格ci,容油量vi。有k个加油站在位置gi,经过一个加油站可以免费加满油且不耗时。车行走有两种模式,1km2min1L或1km1min2L。要租一辆车在t时间内从0到达s,求最少花多少钱。
题解:好坑的题,一开始还搞错了思路,思路想对了倒是挺好做。。 二分出最小的容油量minv,最后比较一下就是了。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define FF(i,a,b) for (int i=a;i<=b;i++) #define F(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 2e5+10; int n, k, s, t; int c[N], v[N], g[N]; bool check(ll x) { ll sum=0; FF(i,1,k) { ll d=g[i]-g[i-1], b=x-d, a=d-b; if(x<d) return false; if(x>=2*d) sum+= d; else sum+= 2*a+b; } return sum<=t; } int main() { scanf("%d%d%d%d", &n, &k, &s, &t); FF(i,1,n) scanf("%d%d", &c[i], &v[i]); FF(i,1,k) scanf("%d", &g[i]); sort(g+1, g+1+k); g[0]=0, g[++k]=s; ll mid, l=1, r=1<<30, minv=INF; while(l<=r) { mid=l+r>>1; if(check(mid)) minv=mid, r=mid-1; else l=mid+1; } int ans=INF; FF(i,1,n) if(minv<=v[i]) ans=min(ans, c[i]); if(ans==INF) puts("-1"); else printf("%d\n", ans); return 0; }