【每日一题】1月12日题目

Mike and distribution

https://ac.nowcoder.com/acm/problem/112024

题意:

给两个长度为n的数组, 要求你找到(n+1)/2个下标,分别为p1, p2,p3....

要求: 图片说明

思路过程:

首先读完题大概可以看出来是贪心, 那么如何贪呢,贪心的话基本都要排序,尤其是这种求对总的贡献的题目,关键在于按什么排序,首先我想到的是按每个下标对的a[i]+b[i] 排序, 并且从大到小来sum1加上每个a[i]然后 sum2加上每个b[i] 当有sum1或者sum2 达标时候,如果是sum1达标, 则从当前位置开始重新排序,按照b[i]的大小重新排序, 反知。
结果wa8了 经过仔细思考后发现,我的想法只是勉强贪心,不够贪心, 必须特别贪心才可以。
于是我看了题解。。。。

这里介绍题解,并且写上我遇到的坑。

题解

  首先我们按照a[i]的大小排序,要记得记录下标与对应的b[i],从大到小排序,首先我们选择a[1],因为 要从n个数字里面选(n/2+1)个我们先把+1 选择了,这时候就把剩下的所有数字两个两个一组, 选择每组里面b[i]更大的那一个就可以了。

图片说明

这里我们观察图片加已理解,首先选择的要比一半多一个,然后选择的2 > sum 我们已经选择了a[1]与b[1] 那么 选择的2 >= sum 就可以了, 多了个等于,
然后我们看图片上面的a数组,选择了a[1] 之后分组无论选择哪一个都符合最后的和*2 大于suma, 这是为什么呢?
因为,a[1]一定大于a[2] 或者 a[3] , 比如我们选择了 1 3 5 7。。。。 1>2 3>4 5>6....
比如我们选择了 1 2 5 6 那么 1>3 2>4 5>6... 所以我们无论选择哪一个a都一定符合
对于数组b来说, 我们在两个中选择大的那一个一定符合。

坑:

主要就是超时问题,我第一步将cin 改为scanf 超时, 我将数组优化 还是超时, 改成快读还是超时,之后发现是重载运算符卡时间了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
ll n;
ll a[maxn], b[maxn];

struct Node
{
    ll a, b,pos;
    bool operator < (Node &p1)
    {
        return p1.a < a;
    }
}t[maxn];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch =='-')flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int main()
{
    n = read();
    for(int i = 1; i <= n; i ++) t[i].a = read();
    for(int i = 1; i <= n; i ++) t[i].b = read(), t[i].pos = i;
    sort(t+1, t+1+n);    
    printf("%d\n",n/2+1);
    printf("%lld ",t[1].pos);
    for(int i = 2; i <= n; i += 2)
    {
        if(t[i].b > t[i+1].b)
            printf("%lld ",t[i].pos);
        else
            printf("%lld ", t[i+1].pos);
    }
    return 0;
}
全部评论

相关推荐

咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
被加薪的哈里很优秀:应该继续招人,不会给你留岗位的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务