首页 > 试题广场 >

配方制作-研发

[编程题]配方制作-研发
  • 热度指数:1242 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解


明明最近迷上了《明日之后》这款游戏。在这款游戏中有一个配方制造系统,玩家可以利用手中的资源和材料,来制造武器和道具。例如,玩家如果需要制造一个小木柜,需要3块木板,而制造一块木板,又需要120个木头和2个小树枝,并且需要走到建筑加工台前制作。而采集木头和小树枝又需要一定的时间。

玩了一段时间之后,明明开始好奇在游戏中做什么最花时间。虽然游戏中已经有标明每个物品的制造时间,但是明明更想通过自己的游戏经历来统计实际需要的时间。明明根据自己的操作,记录下了自己游戏中每个操作事件的开始和结束时间,按时间顺序汇总成了一张表,如下所示:



从上表可以看出,“制造1个小木柜”这个操作,总共用时2000-1=1999秒时间,其中包含两部分:制造3块木板的耗时(1000-5=995秒)和自身的耗时(1999-995=1004秒)。同样的,制造3块木板的995秒耗时中,也包括3部分:收集360个木头的耗时(20-10=10秒)、收集6个小树枝的耗时(40-25=15秒)以及自身耗时(995-10-15=970秒)。在这些操作当中,“制造1个小木柜”自身耗时1004秒,是所有操作中自身耗时最多的一个操作。

明明想知道自己做的这些操作中,哪个操作自身所花的时间是最多的。给出这张事件记录表,你可以帮明明计算一下吗?


数据范围:输入数据组数满足 ,每组数组中操作数满足 ,操作中的数都满足 、 时间结束和开始信息满足
进阶:空间复杂度 ,时间复杂度

输入描述:

输入中包含多组数据。输入的第一行是一个整数T(T<=100),表示后续有多少组测试数据。

每组测试数据第一行是一个整数N(N<=100000),表示记录的行数。随后是N行记录,每行包括3个整数t(030)、e(030)、s(0或1),表示事件的时间、事件的id,以及开始或结束信息(0表示开始,1表示结束)。这些记录按照时间先后顺序给出,任意两行的时间均不相同。保证任意一个事件仅出现一次开始和一次结束,且开始时间在结束之前。保证子任务一定先于父任务结束。




输出描述:

对于每一组测试数据,输出一个整数,表示自身所花时间最多的事件id。如果有多个满足条件的事件,则输出事件id最小的那个。

示例1

输入

1
8
1 1 0
5 2 0
10 3 0
20 3 1
25 4 0 
40 4 1
1000 2 1
2000 1 1

输出

1
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
struct event
{
  int t;
  int e;
  int s;
  int extraTime=0;
};
int test()
{
  int N=0;
  cin>>N;
  //vector<event> eventVec(N);
  stack<event> eventStack;
  int id=0;
  int maxTime=0;
  for(int i=0;i<N;i++)
  {
    int t,e,s;
    cin>>t>>e>>s;
    event inputEvent;
    inputEvent.t=t;inputEvent.e=e;inputEvent.s=s;inputEvent.extraTime=0;
    if(inputEvent.s==0)
      eventStack.push(inputEvent);
    else{
      event tempEvent=eventStack.top();
      int time=inputEvent.t-tempEvent.t;
      //更新最大id
      if(time-tempEvent.extraTime>maxTime)
      {
        id=inputEvent.e;
        maxTime=time-tempEvent.extraTime;
      }
      //相等的情况输出较小的ID,之前少了这两行一个测试用例都没过!!!,加上就全过了......
      else if(time-tempEvent.extraTime==maxTime)
        id=min(id,inputEvent.e);
      eventStack.pop();
      //修改extraTime
      if(!eventStack.empty())
      {
        tempEvent=eventStack.top();
        tempEvent.extraTime+=time;
        eventStack.pop();
        eventStack.push(tempEvent);
      }
    }
  }
  return id;
}
int main()
{
  int T=0;
  cin>>T;
  for(int i=0;i<T;i++)
  {
    cout<<test()<<endl;
  }
  return 0;
}
一个栈搞定,结构体中加了个extraTime用以记录所有子事件花费的时间。
PS:刚开始少加了两行代码,没有判断最大时间相等时取较小的ID这个条件,导致一个用例都没通过。自我怀疑了半天......
发表于 2021-08-06 22:13:39 回复(0)
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		stack<vector<int>> si;//0为入栈,1为出栈
		int level = 0;
		vector<vector<int>> vv;
		while (N--) {
			vector<int> beg(4);//某事件开始
			vector<int> end(4);//某事件结束
			cin >> beg[0] >> beg[1] >> beg[2];
			beg[3] = level;//划分深度,0123
			if (beg[2] == 0) {    //入栈
				si.push(beg);
				level++;
			}
			else {                    //出栈
				vector<int> tmp;    //存储事件
				end = si.top();
				si.pop();
				level--;
				tmp.push_back(beg[0] - end[0]);//总时间
				tmp.push_back(beg[1]);           //id
				tmp.push_back(level);            //深度
				vv.push_back(tmp);
			}
		}
		stack<vector<int>>  s;
		int time = vv[0][0];
		int id = vv[0][1];
		int pre = vv[0][2];
		s.push(vv[0]);
		for (int i = 1; i < vv.size(); i++) {
			if (!s.empty() && vv[i][2] < s.top()[2]) {
				vector<int> temp;
				int t = vv[i][0];
				while (!s.empty() && vv[i][2] < s.top()[2]) {
					t -= s.top()[0];
					s.pop();
				}
				s.push(vv[i]);
				if (t > time) {
					time = t;
					id = vv[i][1];
				}
				else if (t == time) {
					id = min(id, vv[i][1]);
				}
			}
			else {
				s.push(vv[i]);
				if (vv[i][0] > time) {
					time = vv[i][0];
					id = vv[i][1];
				}
				else if (vv[i][0] == time) {
					id = min(id, vv[i][1]);
				}
			}
		}
		cout << id << endl;
	}
	
	return 0;
}


全部通过,栈加栈
编辑于 2021-06-30 13:10:12 回复(0)
C# 通过全部用例,详细注释
using System;
using System.Collections.Generic;

class Program{
    public static void Main(string[] args){
        int groNum = int.Parse(Console.ReadLine());
        while(groNum>0){
            groNum--;
            
            int N = int.Parse(Console.ReadLine());
            int id = -1, time = -1;
            
            Stack<int[]> stack = new Stack<int[]>();
            Stack<int> timeStack = new Stack<int>();
            //处理一组数据
            while(N>0){
                --N;
                //储存一行数据
                string[] temp = Console.ReadLine().Split(" ");
                int[] curr = new int[3];
                for(int i=0; i<3; ++i) curr[i] = int.Parse(temp[i]);
                
                //事件“开始”则入栈
                if(curr[2]==0) {
                    stack.Push(new int[]{curr[0], curr[1]});
                }
                else{
                    //当前事件“结束”的时刻
                    int timeNow = curr[0];
                    //事件的栈顶不是当前事件
                    //说明当前事件包含子事件
                    while(stack.Peek()[1]!=curr[1]){
                        stack.Pop();
                        //减去子事件的耗时
                        timeNow -= timeStack.Pop();
                    }
                    //减去当前事件“开始”的时刻,得到“自身耗时”
                    timeNow -= stack.Peek()[0];
                    //当前事件全部耗时入栈(与“自身耗时”不同)
                    timeStack.Push(curr[0]-stack.Peek()[0]);
                    //记录最长的“自身耗时”
                    if(time<timeNow){
                        time = timeNow;
                        id = curr[1];
                    }
                    //有多个满足条件的事件,则输出事件id最小的
                    else if(time==timeNow) id = Math.Min(id, curr[1]);
                }
            }
            Console.WriteLine(id);
        }
    }
}


发表于 2022-03-18 11:08:05 回复(0)
def fun():
    N = int(input())
    stack = []
    ans = -1
    maxa = float("-inf")
    for _ in range(N):
        t, e, s = map(int, input().split())
        if s == 0:
            stack.append([t, e, 0])
        else:
            tt, ee, st = stack.pop()
            temp = t - tt -st
            if maxa < temp:
                maxa = temp
                ans = ee
            elif maxa == temp:
                ans = min(ans, ee)
            if stack:
                stack[-1][2] += t - tt
    return ans
if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        print(fun())

发表于 2021-08-24 19:27:28 回复(0)
#include <bits/stdc++.h>
using namespace std;

struct event{
    int e;
    int time;
};

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n;
        scanf("%d", &n);
        int last_t;
        int t, e, s;
        stack<event> stk;
        event res = {-1, -1};
        for (int i = 0; i < n; i++){
            scanf("%d %d %d", &t, &e, &s);
            if (i == 0){
                last_t = t;
                stk.push({e, 0});
            }else{
                        // 每到来一组新数据,更新一次栈顶事件所花时间
                int delta = t - last_t;
                        // 如果栈为空,这段时间没做任何事
                if (stk.empty()){
                    stk.push({e, 0});
                    last_t = t;
                    continue;
                }
                event last_e = stk.top();
                stk.pop();
                last_e.time += delta;
                stk.push(last_e);
                if (s == 0){
                    stk.push({e, 0});
                }else{
                    event tmp = stk.top();
                    if (tmp.time > res.time){
                        res = tmp;
                    }else if (tmp.time == res.time){
                        if (tmp.e < res.e){
                            res = tmp;
                        }
                    }
                    stk.pop();
                }
                last_t = t;
            }
        }
        printf("%d\n", res.e);
    }
    
    return 0;
}

发表于 2022-08-26 14:30:49 回复(0)
#include<iostream>
#include<stack>
#include <queue>
#include <vector>
using namespace std;
int main() {
    stack<vector<long long>> st;
    queue<long long> q;
    long long T;
    cin >> T;
    for (long long i = 0; i < T; i++) {
        long long result = 200000; // 自身花时间最小的id
        long long resultTime = 0;
        long long qmin = 1000000; // 最小下标
        long long qmax = -1; // 最大下标
        long long N;
        cin >> N;
        for (long long j = 0; j < N; j++) {
            long long self = 0;
            long long nonself;
            long long t, e, s;
            cin >> t >> e >> s;
            if (s == 0) { // 如果是事件开始
                st.push(vector<long long>({ j, t })); // 保存下标和时间点
            }
            else {
                // 结束事件则弹栈
                vector<long long> begin = st.top();
                st.pop();
                // 计算事件总时间
                long long time = t - begin[1];
                long long selfTime = time; // 默认自身时间为事件总时间
                // 查看队列是否为空
                // 当前事件包裹了中间事件(需要更改 自身时间=总时间-中间事件时间花费)
                if (!q.empty() && begin[0] < qmin && j > qmax) {
                    long long nonselfTime = 0;
                    while (!q.empty()) { // 累加中间的时间
                        nonselfTime += q.front();
                        q.pop();
                    }
                    selfTime = time - nonselfTime; // 计算自身的时间
                }
                // 更新结果
                if (selfTime > resultTime || (selfTime == resultTime && e < result)) {
                    result = e;
                    resultTime = selfTime;
                }

                // 入队(记录当前事件总时间)
                q.push(time);
                // 更新最大最小下标
                qmin = min(begin[0], qmin);
                qmax = max(j, qmax);
            }
        }
        cout << result;
        if (i != T - 1) {
            cout << endl;
        }
        result = 200000; // 自身花时间最小的id
        resultTime = 0;
        qmin = 1000000; // 最小下标
        qmax = -1; // 最大下标
    }
    return 0;
}
求助大佬啊!!!!实在是不知道为什么0个通过,反正测试用例那个是OK的,我也自测了输入多个样例,也没有问题。

发表于 2022-08-09 11:27:34 回复(0)
 还是得使用栈来进行解决,其实这个题有点类似括号匹配的感觉,只有子事件 处理完了,才到自己。






import java.util.*;
public class Main {
 
// 自身耗时=自己结束时间-自己开始时间-别的操作的耗时
 
 
 
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int T=Integer.parseInt(sc.nextLine());
 
        LinkedList<Event> stack=new LinkedList();
 
        while(T-->0){
 
            int n=Integer.parseInt(sc.nextLine());
            int maxOwnTime=0;
            int ret=-1;
            String[] s=sc.nextLine().split(" ");
            Event e=new Event();
            e.startTime=Integer.parseInt(s[0]);
            e.id=Integer.parseInt(s[1]);
            e.status=Integer.parseInt(s[2]);
            stack.push(e);
            for(int i=1;i<n;i++){
 
                // 先检查stack的情况
                String[] s1=sc.nextLine().split(" ");
                Event e1=new Event();
                int time=Integer.parseInt(s1[0]);
                e1.id=Integer.parseInt(s1[1]);
                e1.status=Integer.parseInt(s1[2]);
                if(e1.status==0){ // 说明是事件开始
                    e1.startTime=time;
                    stack.push(e1);
                }
                else{  //说明是事件结束,那么就将栈里的事件弹出来,
                    Event e2=stack.pop();
                    e2.EndTime=time;
                    e2.status=e1.status;
                    e2.totalTime=e2.EndTime-e2.startTime;
                    e2.ownTime=e2.totalTime-e2.otherTime;
                    // 还有id的问题
                    if(e2.ownTime>maxOwnTime){
                        maxOwnTime=e2.ownTime;
                        ret=e2.id;
                    }
                    if(e2.ownTime==maxOwnTime){
                        if(e2.id<ret){
                             ret=e2.id;
                        }
                        
                    }
                    // 此时再看
                    if(!stack.isEmpty()){
                        Event top=stack.peek();
                        top.otherTime+=e2.totalTime; // 还得给这个进行累计。
                    }
                }
            }
           
            
            System.out.println(ret);
            stack.clear();
        }
    }
}
 
// 再用一个栈来进行处理,类似于左右括号匹配的方式来进行
class Event{
    int startTime;
    int EndTime;
 
    int id;
    int status;
    int ownTime;  // 自身耗时=自己结束时间-自己开始时间-别的操作的耗时
    int otherTime;  // 每当stack结束一个其它任务,就从栈头去加上这个数字
    int totalTime;  //结束时间-开始时间
 
 
    public Event(){
 
    }
}



发表于 2022-05-17 11:36:00 回复(0)
终于debug完成了
给大家提供个BFS的版本
#include<iostream>
#include <unordered_map>
#include<map>
#include <queue>
using namespace std;
struct newnode
{
    int t_start;
    int t_end;
    int start;
    int end;
};
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int N;
        cin >> N;
        vector<int> a(N, 0); //记录每一行的节点
        unordered_map<int, newnode> stk; //可以通过节点id找到这个节点的位置、整体时间
        map<int, int>vis; //记录各个节点自身所花的时间
        for (int i = 0; i < N; i++)
        {
            int t, id, s;
            cin >> t >> id >> s;
            a[i] = id;
            if (s == 0)
            {
                stk.insert({ id,{t,0,i,0} });
            }
            else
            {
                stk[id].t_end = t;
                stk[id].end = i;
            }
        }
        //BFS
        queue<newnode>sp;
        //在最外层套上一层 防止无法层序遍历下去
        newnode fir = {0,0,-1,N};
        sp.push(fir);
        while (!sp.empty())
        {
            newnode n = sp.front();
            sp.pop();
            int res = n.t_end - n.t_start;
            int k = n.start + 1;
            int sum = 0;
            while (k != n.end)
            {
                sp.push(stk[a[k]]);
                int temp = stk[a[k]].t_end - stk[a[k]].t_start;
                sum += temp;
                k = stk[a[k]].end + 1;
            }
            if(n.start!=-1)
                vis[a[n.start]] = res - sum;
        }
        //找寻自身花费最大对应的id,vis是map自动排序,所以找到最大值对应的id就行
        int nmax = 0; int index = 0;
        for (auto& i : vis)
        {
            if (i.second > nmax)
            {
                nmax = i.second;
                index = i.first;
            }
        }
        cout << index << endl;
    }
    return 0;
}
这里比较难理解的是要在所有任务外套上一个大任务,目的就是使得一开始层序遍历可以进行下去。
如果不加入话,如果有这样的数据
1 1 0
2 1 0
3 2 0
100 2 0
BFS只会算节点1的,如果套上一个大任务,1,2节点都可以入队列,从而得到正确答案
编辑于 2022-05-10 01:38:32 回复(0)
【求助帖】
在本地IDE、牛客自测能跑样例,但是提交就会出现

“程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)"

模拟了几遍都找不到问题😥
#include <bits/stdc++.h>
using namespace std;

int main(){
    int T;
    cin>>T;
    while(T--){
        int N;
        cin>>N;
        vector<int> time(N/2+1,-1);
        stack<int> work;
        vector<vector<int>> tree(N/2+1);
        for(int i=0;i<N;i++){
            int t,id,p;
            cin>>t>>id>>p;
            if(time[id]!=-1){
                time[id]=t-time[id];
            }else{
                time[id]=t;
            }
            if(!work.empty()){
                if(work.top()==id){
                    work.pop();
                    if(!work.empty()){
                        int index=work.top();
                        tree[index].push_back(id);
                    }else{
                        break;
                    }
                }else{
                    work.push(id);
                }
            }
            else{
                work.push(id);
            }
        }
        for(int i=1;i<time.size();i++){
            for(int j=0;j<tree[i].size();j++){
                time[i]=time[i]-time[tree[i][j]];
            }
        }
        int maxTime=INT_MIN;
        int maxWork=-1;
        for(int a=1;a<time.size();a++){
            if(time[a]>maxTime){
                maxTime=time[a];
                maxWork=a;
            }
        }
        cout<<maxWork<<endl;
    }
    return 0;
}


发表于 2022-04-14 23:46:51 回复(0)
递归解法
#include<bits/stdc++.h>
using namespace std;

struct node
{
	int t,id,w;
}a[100005];

int k;
int sum[100005];
int temp;
int dfs(int l)
{
	int r = l+1;
	while(a[l].id != a[r].id)
	{
		sum[l] += dfs(r);//第i个事件的子事件花费的时间 
		r = temp;
	}
	sum[l] = (a[r].t - a[l].t) - sum[l];//第l个事件自身花费时间 
	temp = r+1;
	return a[r].t - a[l].t;//返回所有当前事件的总用时 
}
int main()
{
	int t,n;
	cin >> t;
	while(t--)
	{
		cin >> n;
		for(int i = 1; i <= n; i++)
		{
			cin >> a[i].t >> a[i].id >> a[i].w;
		}
		dfs(0);
		int maxn = 0;
		int id = 0;
		for(int i = 1; i <= n; i++)
		{
			if(maxn < sum[i])
			{
				maxn = sum[i];
				id = a[i].id;
			}
			else if(maxn == sum[i] && id > a[i].id)
			{
				id = a[i].id;
			}
			sum[i] = 0;
			a[i].id = 0;//不清零会发生段错误 
		}
		sum[0] = 0;
		sum[n+1] = 0;
		cout << id << "\n";
	}
}

sum【i】 = 第i个事件的所有子事件花费时间,同一个id可能出现两次,这里只处理开始时间,结尾时间不需要再次计算
l = 当前事件的开始时间
r = 当前时间的结束时间
temp = 储存结束时间以返回至上次调用
dfs = 该区间的子区间
尝试匹配当前事件
如果目前事件包含子事件,先处理子事件
处理完后令r右移,再次判断是否匹配,如果还不匹配,则再次计算子事件用时
dfs(0):假设一个包含所有事件的超级事件,如果从1开始则无法处理以下数据
1
6
1 1 0
2 1 1
3 2 0
4 2 1
5 2 0
8 2 1
发表于 2021-08-06 20:21:37 回复(0)
第一个栈记录还未完结的事件和已完成但时间亲生父亲还未完结的事件,第二个栈记录子事件的事件。
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T>0){
            --T;
            int N = in.nextInt();
            int id = -1, time = -1;
            Deque<int[]> stack = new LinkedList<>();
            Deque<Integer> timeStack = new LinkedList<>();
            while(N>0){
                --N;
                int[] curr = new int[3];
                for(int i=0; i<3; ++i) curr[i] = in.nextInt();
                if(curr[2]==0) {
                    stack.push(new int[]{curr[0], curr[1]});
                }
                else{
                    int timeNow = curr[0];
                    while(stack.peek()[1]!=curr[1]){
                        stack.pop();
                        timeNow -= timeStack.pop();
                    }
                    timeNow -= stack.peek()[0];
                    timeStack.push(curr[0]-stack.peek()[0]);
                    if(time<timeNow){
                        time = timeNow;
                        id = curr[1];
                    }
                    else if(time==timeNow) id = Math.min(id, curr[1]);
                }
            }
            System.out.println(id);
        }
    }
}
发表于 2021-07-17 20:35:19 回复(0)
就用栈+树就运行超时就离谱....
T=int(input().strip())
for t in range(T):           #有T组测试数据
    N=int(input().strip())   #该组测试数据有N行
    D={}                          #D保存各个事件ID以及其自身耗时
    A=[]                 
    parent_list=[]                #parent_list保存各个事件的父活动
    Tree={}                       #Tree保存事件父子树(父亲ID以及其各个孩子ID)
    for n in range(N):
        tmp=list(map(int,input().strip().split()))
        if tmp[2]==1:             #遇到1出栈
            if len(A)>0 and A[-1][-1]==0: 
                t=A[-1] 
                A.pop() 
                D[tmp[1]]=tmp[0]-t[0]  #计算各个事件的自身耗时        
        else: 
            A.append(tmp)         #遇到0入栈
            if len(A)>=2:
                parent=A[-2][1]         #父亲
                child=A[-1][1]          #孩子
                if parent not in parent_list:
                    parent_list.append(parent)
                    Tree[parent]=[child]
                else:
                    Tree[parent]=Tree[parent]+[child]

    for t in Tree:
        for i in range(len(Tree[t])):
            D[t]=D[t]-D[Tree[t][i]]     #父活动的总耗时=自身耗时-所有孩子的自身耗时
    sd=sorted(D)  #确保小id在前
    maxT=0
    for k in range(len(sd)):
        if D[sd[k]]>maxT:
            maxT=D[sd[k]]
            index=sd[k]
    print(index)


编辑于 2021-05-21 16:57:14 回复(0)