第二题O(N)复杂度过的 不用二分
我们容易发现单调性 为了凑够美味度 从美味度从大到小 热量是具有单调递减特性的(举个例子 如果你5热量可以满足7美味度 那么5热量肯定满足<=7的美味度) 那么我们维护一个MINN数组从大到小维护 下标 i 代表至少达到i美味度你需要吃的热量 那么维护的时候 MINN[i] = min(MINN[I+1],MINN[i])
代码里有个快排 这个是没必要的快排(现已修整) 可以去掉 所以也就是O(N)复杂度
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 200025; struct node { int x,y; bool operator < (const node other) { return y < other.y; } }arr[MAX_N]; struct tmpnode { int x,y; }brr[MAX_N]; int MINN[MAX_N]; int main() { memset(MINN,0x3f,sizeof(MINN)); int n,m,k,ans = -1; scanf("%d%d%d",&n,&m,&k); for(int i = 1;i<=n;++i) { scanf("%d%d",&arr[i].x,&arr[i].y); if(arr[i].y>=k) { if(ans==-1) ans = arr[i].x; else ans = min(ans,arr[i].x); } } for(int i = 1;i<=n;++i) { MINN[arr[i].y] = min(MINN[arr[i].y],arr[i].x); } for(int i = 100000;i>=0;--i) { MINN[i] = min(MINN[i+1],MINN[i]); } for(int i = 1;i<=m;++i) { scanf("%d%d",&brr[i].x,&brr[i].y); if(brr[i].y>=k) { if(ans==-1) ans = brr[i].x; else ans = min(ans,brr[i].x); } } for(int i = 1;i<=m;++i) { if(brr[i].y>=k) continue; else { if(ans == -1) ans = MINN[k-brr[i].y]+brr[i].x; else ans = min(ans,MINN[k-brr[i].y]+brr[i].x); } } if(k==0) { printf("0\n"); return 0; } if(ans>=200000) { printf("-1\n"); return 0; } printf("%d\n",ans); return 0; }
全部评论
(8) 回帖