首页 > 其他分享 >2023-07-22:一共有n个项目,每个项目都有两个信息, projects[i] = {a, b}, 表示i号项目做完要a天,但是当你投入b个资源,它就会缩短1天的时间, 你一共有k个资源,你的目

2023-07-22:一共有n个项目,每个项目都有两个信息, projects[i] = {a, b}, 表示i号项目做完要a天,但是当你投入b个资源,它就会缩短1天的时间, 你一共有k个资源,你的目

时间:2023-07-22 20:55:35浏览次数:36  
标签:22 项目 int days project 一共 ans projects

2023-07-22:一共有n个项目,每个项目都有两个信息,

projects[i] = {a, b},

表示i号项目做完要a天,但是当你投入b个资源,它就会缩短1天的时间,

你一共有k个资源,你的目标是完成所有的项目,但是希望总天数尽可能缩短。

在所有项目同时开工的情况下,返回尽可能少的天数。

1 <= n <= 10^5,

1 <= k <= 10^7。

答案2023-07-22:

以下是代码的大致过程和功能描述:

1.导入所需的包:fmt 用于打印输出,math 用于数学运算。

2.定义函数 minDays,该函数接受项目详情和可用资源数量作为输入参数。

3.初始化变量 lr,用于跟踪搜索范围的左右边界。

4.遍历项目列表,并更新 r 的值为当前 r 和项目完成时间 (project[0]) 中的最大值。

5.将变量 mans 初始化为 r,作为找到的目标最少天数的初始猜测。

6.使用二分搜索算法找到最小天数。重复以下步骤,直到 l 小于等于 r

  • 计算中间值 m,即 lr 的平均值。

  • 如果在 m 天或更少的时间内完成所有项目所需的总资源量 (yeah(projects, m)) 小于等于可用资源量 k,则更新 ansm,并将右边界 r 调整为 m - 1

  • 否则,将左边界 l 调整为 m + 1

7.返回 ans 的最终值,表示完成所有项目所需的最少天数。

8.定义 yeah 函数,该函数接受项目详情和天数作为输入参数。

9.初始化变量 ans,用于跟踪所有需要的资源总量。

10.遍历项目列表,并计算超过给定天数的每个项目所需的资源量。

11.将每个项目所需的资源量添加到 ans

12.返回 ans 的最终值,表示超过给定天数的所有项目所需的资源总量。

13.在 main 函数中,创建一个示例项目数据集 project,其中包含项目的详细信息。

14.将可用资源 k 设置为特定值。

15.打印调用 minDays 函数并传入项目数据集和可用资源作为参数的结果。

总的时间复杂度:

  • minDays 函数中的二分搜索算法的时间复杂度为 O(log(r)),其中 r 是最大项目完成时间。

  • yeah 函数中的遍历项目列表的时间复杂度为 O(n),其中 n 是项目的数量。

因此,总的时间复杂度为 O(log(r) + n)。

总的空间复杂度:

  • 空间复杂度主要来自于变量的存储和函数调用的堆栈空间。

  • 不考虑输入数据的空间占用,变量和数据结构的空间复杂度是常数级的,不随输入规模的增长而变化。

  • 函数调用的堆栈空间复杂度是 O(log(r) + n),其中 r 是最大项目完成时间,n 是项目的数量。

因此,总的空间复杂度可以近似为 O(log(r) + n)。

go完整代码如下:

package main

import (
	"fmt"
	"math"
)

func minDays(projects [][]int, k int) int {
	l := 0
	r := 0
	for _, project := range projects {
		r = int(math.Max(float64(r), float64(project[0])))
	}
	m, ans := r, r
	for l <= r {
		m = (l + r) / 2
		if yeah(projects, m) <= k {
			ans = m
			r = m - 1
		} else {
			l = m + 1
		}
	}
	return ans
}

func yeah(projects [][]int, days int) int {
	ans := 0
	for _, p := range projects {
		if p[0] > days {
			ans += (p[0] - days) * p[1]
		}
	}
	return ans
}

func main() {
	project := [][]int{{1, 2}, {3, 4}, {5, 6}}
	k := 4
	fmt.Println(minDays(project, k))
}

在这里插入图片描述

rust完整代码如下:

fn main() {
    let project = vec![vec![1, 2], vec![3, 4], vec![5, 6]];
    let k = 4;
    println!("{}", min_days(&project, k));
}

fn min_days(projects: &Vec<Vec<i32>>, k: i32) -> i32 {
    let mut l = 0;
    let mut r = 0;
    for project in projects {
        r = r.max(project[0]);
    }
    let mut ans = r;
    while l <= r {
        let m = (l + r) / 2;
        if yeah(projects, m) <= k {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    ans
}

fn yeah(projects: &Vec<Vec<i32>>, days: i32) -> i32 {
    let mut ans = 0;
    for p in projects {
        if p[0] > days {
            ans += (p[0] - days) * p[1];
        }
    }
    ans
}

在这里插入图片描述

c++完整代码如下:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int yeah(vector<vector<int>>& projects, int days);

int minDays(vector<vector<int>>& projects, int k) {
    int l = 0;
    int r = 0;

    for (auto project : projects) {
        r = max(r, project[0]);
    }

    int m, ans = r;

    while (l <= r) {
        m = (l + r) / 2;
        if (yeah(projects, m) <= k) {
            ans = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

int yeah(vector<vector<int>>& projects, int days) {
    int ans = 0;
    for (auto p : projects) {
        if (p[0] > days) {
            ans += (p[0] - days) * p[1];
        }
    }
    return ans;
}

int main() {
    vector<vector<int>> projects = { {1, 2}, {3, 4}, {5, 6} };
    int k = 4;

    int result = minDays(projects, k);

    cout << result << endl;

    return 0;
}

在这里插入图片描述

c完整代码如下:

#include <stdio.h>

int minDays(int projects[][2], int size, int k) {
    int l = 0;
    int r = 0;

    for (int i = 0; i < size; i++) {
        r = (projects[i][0] > r) ? projects[i][0] : r;
    }

    int m, ans = r;
    while (l <= r) {
        m = (l + r) / 2;
        if (yeah(projects, size, m) <= k) {
            ans = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

int yeah(int projects[][2], int size, int days) {
    int ans = 0;
    for (int i = 0; i < size; i++) {
        if (projects[i][0] > days) {
            ans += (projects[i][0] - days) * projects[i][1];
        }
    }
    return ans;
}

int main() {
    int projects[][2] = { {1, 2}, {3, 4}, {5, 6} };
    int size = sizeof(projects) / sizeof(projects[0]);
    int k = 4;

    int result = minDays(projects, size, k);
    printf("Result: %d\n", result);

    return 0;
}

在这里插入图片描述

标签:22,项目,int,days,project,一共,ans,projects
From: https://www.cnblogs.com/moonfdd/p/17574224.html

相关文章

  • 2023.7.22 周六:封装
    1//类2publicclassStudent{3privateStringname;4privateintage;5publicvoidsetName(Stringname)6{7this.name=name;8}9publicStringgetName()10{11returnthis.name;12}13......
  • 2023-07-16~07-22第二周暑假生活
    本周平均学习时间为3小时每天,大部分时间在学习CSScss通过伪类伪元素动画效果可以实现许多有趣的动画;动画元素为animotion;在css中一般这样定义:animation:nameattribute1attribute2...;/*attribute可以省略*/@keyframesname{/*具体实现*/0%{/*动画时间进行到0%的效果*/}10......
  • 7.22
    今天吃饭饿死了,中午吃的炒饼,除了有点咸还是不错的,相比于前两天的伙食。然后就是没吃饱中间又去加了两次饭,后来没了,又去拿了两个肉包子,反正这天中午是我吃的最爽的一次,要是吃完饭后还不用带小孩出门口就更好了......
  • python获取当前项目根目录
    defget_item_path(item_name):""":paramitem_name:项目名称,如pythonProject:return:项目根目录"""#获取当前所在文件的路径cur_path=os.path.abspath(os.path.dirname(__file__))#获取根目录returncur_path[:cur_path.......
  • 7.22
    数字三角形#include<bits/stdc++.h>//#defineintlonglongusingnamespacestd;constintN=1e4+10,mod=1e9+7;strings;intn,t,a[N][N],f[N][N],res,num,ans,m;boolvis[N];signedmain(){std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);......
  • 暑假周记(7.22)
    哇,今天在床上几乎躺了一天方法里面调用方法构造方法中可以访问其他的构造方法构造方法中可以访问实例方法,默认this.实例方法,也可以省略this构造方法中可以访问静态方法,默认类名.静态方法,也可以this.静态方法,可以省略类名/this实例方法中可以访问构造方法,new+构造方法();实例......
  • 洛谷 P8490 [IOI2022] 鲶鱼塘
    洛谷传送门LOJ传送门不算很难的题,但是调起来比较恶心。下文默认下标从\(1\)开始。设第\(i\)列长堤的高度为\(h_i\)。考虑观察一些性质。Observation1:若\(h_{i-1}<h_i>h_{i+1}\),那么\(h_i=n\)一定不劣。若\(h_i<n\),\([h_i+1,n]\)的鱼是抓不到的,并......
  • 2023年7月22日 天气:晴
       今天早上起来背了一个小时的英语单词,然后晨跑了三公里,回到家后学习了一个小时的 英语阅读。下午学习编程了一个小时,然后看了一会电视,最后就是写了一个小时的作业,晚上练了一个小时的字,最后看了几章小说。   明天打算看几集电视剧,然后学习一个小时的java,有时间的......
  • idea启动项目发现端口被占用!!!导致启动不起来
    windows端口被占用netstat-ano|findstr端口号任务管理器详细信息PID排序找到刚才查到的右键结束原因:idea被异常终止导致tomcat没死......
  • 2023/7/22
    今天主要就是做了3道题,由于第三题的思路开始错了,花的时间比较多,从网页的答题框复制出来有点。微博上有个自称“大笨钟V”的家伙,每天敲钟催促码农们爱惜身体早点睡觉。不过由于笨钟自己作息也不是很规律,所以敲钟并不定时。一般敲钟的点数是根据敲钟时间而定的,如果正好在某个整点......