拼多多笔试 第三题真O(N)复杂度过的 不用二分
第二题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;
}
海康威视公司氛围 515人发布