专栏首页落影的专栏程序员进阶之算法练习(五十一)

程序员进阶之算法练习(五十一)

正文

题目1

题目链接 题目大意: 给出一个图形,下面是n=1、2、3、4的时候:

现在需要把上面的图形染色,由若干个菱形组成; 问,有多少种染色方法?

输入: 第一行,整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行,整数? (1≤?≤10^9).

输出: 每个样例一行,染色的方法数量。

Examples input 2 2 1 output 2 1 样例解释: 对于样例1,当n=2的时候一共有2种染色方法:

对于样例2,当n=1的时候,只有1种染色方法:

题目解析: 找规律的问题,先从n=1开始考虑,只有一种方案; n=2的时候,我们可以采用染色方案1,将第一个竖着的菱形染色;也可以先上下斜着放,将第二个竖着的菱形染色; 同理n=3时,有将第1、2、3个菱形染色的方案; 总结规律, ans=n;

代码实现:

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << n << endl;
    }   
    
    return 0;
}

题目2

题目链接 题目大意: 有n个砝码,每个砝码的重量是一样的; 由于砝码的重量标识已经模糊,只能大概知道的重量区间是在 [a-b, a+b]这个区间内; 现在想知道,这n个砝码的重量,能否在区间[c-d, c+d]内; 如果可以,则输出YES;如果不可以,则输出NO;

输入: 第一行,整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行,5个整数 n,?,?,?,? (1≤?≤1000, 0≤?<?≤1000, 0≤?<?≤1000)

输出: 每个样例一行,如果可以,则输出YES;如果不可以,则输出NO;

Examples input 5 7 20 3 101 18 11 11 10 234 2 8 9 7 250 122 19 41 21 321 10 3 10 8 6 1

output Yes No Yes No Yes

题目解析: 因为a和b比较小,枚举下a和b的区间,可以解决问题;

但是假如,a和b很大呢?(0≤?<?≤10^9, 0≤?<?≤10^9) 我们用[l, r]来表示[c-d, c+d]的区间; 我们用[gapL, gapR] 来表示[(a-b)n, (a+b)n]的区间; 只要这俩个区间有重叠,则表示存在可能性; 这样就不用枚举,复杂度从O(N^2)变成O(1)。

代码实现:

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        lld n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        lld l = (c - d), r = (c + d);
        lld ans = -1;
        lld gapL = (a - b) * n, gapR = (a + b) * n;
        bool ok = 0;;
        if (gapL <= l && l <= gapR) {
            ok = 1;
        }
        else if (gapL <= r && r <= gapR) {
            ok = 1;
        }
        else if (l <= gapL && gapL <= r) {
            ok = 1;
        }
        else if (l <= gapR && gapR <= r) {
            ok = 1;
        }
        if (ok) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }   
    
    return 0;
}

题目3

题目链接 题目大意: 有n个整数组成的数组,现在对数组的元素重新组织,希望新的数组满足: |?[1]−?[2]| ≤ |?[2]−?[3]| ≤ … ≤ |?[?−1]−?[?]| 求新的数组。

输入: 第一行,整数?表示有t个样例数量 (1≤?≤1000) 接下来每t个样例,第一行, 整数? (3≤?≤10^5) 第二行是n个整数,?1,?2,…,?? (−10^9≤??≤10^9).

输出: 每个样例一行,新数组的n个整数;

Examples input 2 6 5 -2 4 8 6 5 4 8 1 4 2 output 5 5 4 6 8 -2 1 2 4 8

题目解析: 假设n个数字散落在一维数轴上,那么任意两个数字的绝对值之差,就是两个数字在数轴之间的间距; 题目的问题转化为,求一个排列,使得相邻两个数字的间距越来越大; 假设从小到大排序完之后,数组是a[N];容易知道,所有数字中间距的是a[n]-a[1],那么可以将这个数字放到最右边; 同理,第二大的数字要么是a[1]和a[n-1],要么是a[2]和a[n],我们任取其中一种,假设是a[1]和a[n-1]; 同理,第三大的数字就是a[2]和a[n-1]; 同理,第四大的数字就是a[3]和a[n-1]; 如此交替选择,会使得间距越来越小,得到了一种满足题意的解法;

代码实现:

int a[N];
int ans[N];

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) cin >>a[i];
        sort(a, a + n);
        int l = 0, r = n - 1, k = n - 1;
        while (l <= r) {
            ans[k--] = a[r--];
            if (l <= r) {
                ans[k--] = a[l++];
            }
        }
        for (int i = 0; i < n; ++i) {
            cout << ans[i] << " ";
        }
        cout << endl;
    }   
    
    return 0;
}

题目4

题目链接 题目大意: n个数字的数组,如果某个数字比相邻左右两个数字大,则称为峰;

从n个数字里面选出连续的k个数字,希望包括尽可能多的山峰; 如果有多种可能,使得第一个位置尽可能小;

输入: 第一行,整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例第一行,整数n和k (3≤?≤?≤2⋅1e5) 第二行n个整数, ?1,?2,…,?? (0≤??≤1e9, ?? ≠ ?[?+1])

输出: 每个样例一行,输出整数t和l,分别表示k个连续数字最多能被峰分为几部分,以及区间开始位置;

Examples input 2 8 6 1 2 4 1 2 4 1 2 5 3 3 2 3 2 1

output 3 2 2 2

样例解释: 样例一选择的数字区间是[2, 7],峰的数字有4和4,可以把区间分为3部分,区间开始位置是2; 样例二的区间是[2, 4],峰的数字只有3,可以把区间氛围2部分,区间开始位置是2; 题目解析: 先找出所有的山峰,假设是m个,遍历这些山峰; 对于第1个山峰,直接放入队列q; 对于第2个山峰,直接放入队列q,接下来判断队列中的距离是否超过k:如果满足q.back() - q.front() + 2 >= k 则表示队列中山峰已经无法用连续的k个数字来包括; 此时需要pop掉队头的山峰,也是最早加入的数字。

每加入一个数字到山峰,检查完队列数字的合法性,接着计算这个队列的结果是否更优;

代码实现:

int a[N];
queue<int> q;

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        while (!q.empty()) {
            q.pop();
        }
        
        int ans = 0, start = 0;
        for (int i = 1; i < n - 1; ++i) {
            if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
                q.push(i);
                while (q.back() - q.front() + 2 >= k) {
                    q.pop();
                }
                if (q.size() > ans) {
                    ans = q.size();
                    start = q.back() + 1 - (k - 1);
                }
            }
        }
        cout << ans + 1 << " " << max(0, start) + 1 << endl;
    }   
    
    return 0;
}

题目5

题目链接 题目大意: 给出n个整数的数组,现在每秒可以对数组进行一次操作: 第x秒,可以从数组中选择出来若干个数,将每个数加上2^(x-1);

现在希望数组满足?1≤?2≤…≤?? ,问最少需要多少秒;

输入: 第一行,整数?表示有t个样例数量 (1≤?≤1000) 接下来t个样例,第一行,整数? (1≤?≤10^5) 第二行,n个整数 ?1,?2,…,?? (−109≤??≤109).

输出: 最少需要秒数;

Examples input 3 4 1 7 6 5 5 1 2 3 4 5 2 0 -4 output 2 0 3

题目解析: 按照题意,分别可以加上数字1、2、4、8、16、、、 由于数字递增很快(指数级),可以遇见不会添加很多次; 那么可以考虑暴力来解决,枚举x=0、1、2、3、4、5、6的情况是否满足要求,每次枚举的复杂度是O(NLogM);M是数字大小,最多枚举LogM次;

接着,需要找一种能快速验证,当x=k的时候,是否满足要求; 由贪心的思想,我们知道对于数字a[n],由于预期a[n]是最大的数字,可以直接将所有的数字加到a[n]上; 对于数字a[n-1],我们希望a[n-1]在满足a[n-1]<=a[n]的情况下,尽可能的大; 同理,我们希望a[n-2]、a[n-3]、、、都是如此的处理;

那么问题变成,如何保证a[i-1]在满足a[i-1]<=a[i]的情况下,a[i-1]尽可能的大? 答案就是:从大到小的加数字(2^(x-1)),直到数字无法添加,此时数字就是最大;

注意,这里不是从小到大;比如说数字6变成12,如果从大到小有6+4+2=12,但是如果变成从小开始,则会出现取了数字1、2之后,无法取4,最大值就是9;

代码实现:

typedef long long lld;
lld p[N];
lld a[N];

bool check(int n, int k) {
    lld last = llinf;
    for (int i = n - 1; i >= 0; --i) {
        lld tmp = a[i];
        for (int j = k; j >= 1; --j) {
            if (tmp + p[j-1] <= last) {
                tmp += p[j - 1];
            }
        }
        if (tmp > last) {
            return false;
        }
        last = tmp;
    }
    return true;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    p[0] = 1;
    for (int i = 1; i < 31; ++i) p[i] = p[i-1] * 2;
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        int k = 0;
        while (1) {
            if (check(n, k)) {
                cout << k << endl;
                break;
            }
            k++;
        }
    }   
    
    return 0;
}

总结

题目1是找规律,注意看样例; 题目2是区间重叠,其实是判断两个区间是否存在重叠; 题目3是构造,需要一点点想法,借住数轴更容易想通; 题目4是贪心,尽量保证最长的一个队列,然后枚举每一个位置; 题目5是暴力+贪心,发现题目计算次数不多,寻找一个快速验证的方法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员进阶之算法练习(十五)

    前言 有朋友推荐一个新的算法练习网站leetcode,说北美的公司招人都是400题起步,国内公司招聘也经常用到,上海的尤其多。 很有意思,可以花点时间做做le...

    落影
  • 程序员进阶之算法练习(二十五)

    前言 算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意: 给出a、b、c三种材料,可以1:2:4组成...

    落影
  • 程序员进阶之算法练习(四十五)

    每个路口的机动车道有三个方向,分别是左转、直行、右转,同时路口有一条人行道; 每行输入有四个数字l,s,r,p,分别表示左转、直行、右转、人行道的交通信号灯是...

    落影
  • 程序员进阶之算法练习(五十三)

    题目链接 题目大意: 有三堆石头,分别有a、b、c个; 现在可以执行操作: 1、从第一堆拿出1个石头,第二堆拿出2个石头; 2、从第二堆拿出1个石头,...

    落影
  • 程序员进阶之算法练习(五十二)

    题目链接 题目大意: n个人参加比赛,每个人都有一个分数a[i],现在需要给这些人发奖牌(每个人最多发一个),要求:

    落影
  • 程序员进阶之算法练习(五)

    前言 这次的题目质量非常高,除了第一道签到题之外都是很不错的想法题,值得学习。 几乎所有的程序员都能做A题; 思维缜密的程序员可以做B题; 数学还没还给老师的能...

    落影
  • 程序员进阶之算法练习(三十一)

    BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。

    落影
  • 程序员进阶之算法练习(二十一)

    前言 转眼已经到5月,可是我还没订17年的计划,真是悲伤的故事。 今年还是想花点时间,玩玩题目。 题目不会太简单,也不会太难,简单的如1、2题,难的如3、...

    落影
  • 程序员进阶之算法练习(四十一)

    题目链接 题目大意: 有一个由数字0、1组成的字符串,长度为n; 现在需要将其切分成若干段,要求每一段0和1的数量是不相同的。 比如说1, 101, 0...

    落影

扫码关注云+社区

领取腾讯云代金券