程序员进阶之算法练习(三)

前言

看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。

A

题目链接 题目大意:n个数字,找出连续一串上升序列的长度。 代码实现

    int maxNum = 1, k = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i] > a[i - 1]) {
            ++k;
            maxNum = max(maxNum, k);
        }
        else {
            k = 1;
        }
    }

题目解析: 对于一串序列,假如是以a[i]结尾,如果a[i+1] > a[i] 那么a[i+1]会让序列+1;如果a[i+1] <= a[i] 那么a[i+1]会重新开始新的序列。

B

题目链接 题目大意:给出n个数字,寻找a[i] + a[j] = 2^x,并且i < j。算出总共有多少对存在?

方法1

代码实现

    for (int i = 0; i < n; ++i) {
        long long k = 1;
        while (k <= a[i]) {
            k = k << 1;
        }
        k -= a[i];
        
        long long left = 0, right = i - 1;
        long long l = left, r = right;
        while (left < right) { // 寻找 == k的左边界
//            printf("%d %d %d \n", i, left, right);
            long long mid = (left + right) / 2;
            if (a[mid] > k) {
                right = mid - 1;
            }
            else if (a[mid] < k) {
                left = mid + 1;
            }
            else {
                l = mid;
                right = mid;
            }
        }
//        printf("%d %d %d \n ------ \n", i, left, right);
        if (a[left] == k) {
            l = left;
        }
        left = 0;
        right = i - 1;
        while (left < right) { //选择 == k的右边界
//            printf("%d %d %d \n", i, left, right);
            long long mid = (left + right) / 2;
            if (a[mid] > k) {
                right = mid - 1;
            }
            else if (a[mid] < k) {
                left = mid + 1;
            }
            else {
                r = mid;
                left = mid + 1;
            }
        }
//        printf("%d %d %d \n", i, left, right);
        if (a[right] == k) {
            r = right;
        }
        
        if (a[l] == k && a[r] == k && r >= l) {
            count += r - l + 1;
//            if (a[l] == a[i]) {
//                --count; // 排除自己
//            }
        }

题目解析: 对数组进行从小到大排序,假设有a[i] + a[j] = 2 ^x,并且i < j,x为大于a[j]的最小的2的幂。 那么在[1, j - 1]的区间内,不存在a[i] + a[j] = 2 ^ (x - 1)和 a[i] + a[j] = 2 ^ (x + 1)。 故而排序后,对于a[j],只要求出值为(2^x - a[j])的区间即可。用二分查找。

方法2

代码实现

#include <map>
map<int,int> M;
long long ans=0;
int main(){
    int n,a;
    cin>>n;
    while(n--){
        cin>>a;
        for(int i=0;i<=31;i++)  ans+=M[(1LL<<i) - a];
        M[a]++;
    }
    cout<<ans;
}

题目解析: 对于每个数,只考虑前面的组合。 已知,最大数字不会超过2^31,那么对于每个数字枚举一遍即可,用map来存之前出现的数字。

C

题目链接 题目大意:给出n个目标点,m个源点,求最小的r,使得每个目标点的r范围内至少存在一个源点。 代码实现

    long long ret = (long long)2 * 10E9;
    long long left = 0, right = ret;
    while (left < right) {
        long long mid = (left + right) / 2;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            while (j < m) {
                if (a[i] >= b[j] - mid && a[i] <= b[j] + mid) {
                    break;
                }
                ++j;
            }
        }
        if (j < m) {
            ret = mid;
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }

题目解析: 对目标点和源点排序。 易知,r具有线性特点,即如果r可行,那么r+1必然可行。可以用二分。 同时,目标点i对应的源点为j,那么有i+1目标点的源点>=j。

D

题目链接 题目大意:从起点到终点的距离为d,骑车速度为a秒/公里,走路速度为b秒/公里(a < b)。车子每走k公里就要修理一次,时间为t秒。车子最初k公里不需要修理,问最短的时间到达终点。 代码实现

    long long d, k, a, b, t;
    cin >> d >> k >> a >> b >> t;
    
    if (d <= k) {
        ret = d * a;
    }
    else {
        
        d -= k;
        ret = a * k;
        
        long long left = d % k;
        long long c = d / k;
        
        ret += min(k * a + t, k * b) * c;
        
        ret += min(t + left * a, left * b);
    }

题目解析: 先让车子走k公里(因为a<b),接下来把剩下的路分成若干段,每段k公里,最后剩下的部分为left公里。 对于每段的k公里,根据k * a + t 和 k * b 的大小决定走路还是骑车; 最后的left公里,根据t + left * a 和 left * b的大小决定走路还是骑车;

是否存在前面走路,后面骑车的情况? 假设最后一段是骑车,那么前面的k公里必然也是骑车。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

I'm Telling the Truth(二分图)- HDU 3729

二分图:设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点...

9540
来自专栏专知

【Code】关关的刷题日记21——Leetcode 485. Max Consecutive Ones

关小刷刷题 21——Leetcode 485. Max Consecutive Ones 题目 Given a binary array, find the m...

303100
来自专栏窗户

scheme实现最基本的自然数下的运算

  教一个基本没编过什么程序的朋友scheme,为什么教scheme呢?因为他想学,因为一直听我鼓吹,而他觉得他自己多少有C语言一点基础,而又因为我觉得函数式才...

9130
来自专栏令仔很忙

设计模式六大原则——里氏替换原则(LSP)

       里氏替换原则(LSP,Liskov Substitution Principle)是关于继承机制的原则,是实现开放封闭原则的具体规范,违反了里氏替...

17410
来自专栏Fish

UVA-12108 Extraordinarily Tired Students

啊,题也是很长很长的,让我怀疑这个ACM是不是也顺带着考英语阅读。 不过题意比较简单,就是课上有n(n<=10)个学生,每个人都有个清醒-睡眠周期,每个人都是先...

22170
来自专栏专知

【LeetCode 242】 关关的刷题日记36 Valid Anagram

关关的刷题日记36 – Leetcode 242. Valid Anagram 题目 Given two strings s and t, write a fu...

36090
来自专栏数据结构与算法

BZOJ1569: [JSOI2008]Blue Mary的职员分配(dp 暴力)

14450
来自专栏专知

【 关关的刷题日记47】Leetcode 38. Count and Say

关关的刷题日记47 – Leetcode 38. Count and Say 题目 The count-and-say sequence is the sequ...

324100
来自专栏云霄雨霁

设计模式----抽象工厂模式

15500
来自专栏行者常至

golang string、int、int64 float 互相转换

18730

扫码关注云+社区

领取腾讯云代金券