QQ扫一扫联系
火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有 9 趟列车,在入口处按照 { 8,4,2,5,3,9,1,6,7 } 的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?
时间限制:5000
内存限制:65536
输入
输入第一行给出一个整数 N (2 ≤ N ≤ 105),下一行给出从 1 到 N的整数序号的一个重排列。数字间以空格分隔。
输出
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
样例输入
9 8 4 2 5 3 9 1 6 7
样例输出
4
实验室使用排期
题目收集中……
负载均衡
负载均衡是指在一组后端服务器上有效地分配传入的网络流量。负载均衡算法按照某种特定方法分配负载。
如果我们可以估算出最大的传入流量负载,则可以根据以下规则设计算法:
- 大小为S的传入流量负载将首先被分解为两块,并且每块可以再次被分解为两块,以此类推。
- 每轮只做一次分解。
- 在任何时候,最小负载的规模必须严格大于最大负载规模的一半。
- 所有的规模都是正整数。
- 这个分解过程会一直进行下去,直到不可能再进行任何分解。
例如,如果S=7,那么我们可以先将其分解为3+4,然后继续分为4=2+2。这个分解终止时,我们需要3台服务器,其负载分别为3、2、2。
本题要求此算法所需的后端服务器的最大数量。由于分解可能不是唯一的,因此请找到最佳解决方案 —— 即使最大和最小规模之间的差异最小化的解。
时间限制:9000
内存限制:65536
输入
输入给出一个正整数 S(2 ≤ S ≤ 200),为传入流量负载的规模。
输出
在一行中输出两个数字:M 为所需的后端服务器的最大数量;D 为使用了 M 个服务器的解决方案中,最大和最小规模之差的最小值。一行中的数字间必须以一个空格分隔,行的开头或结尾不能有多余的空格。
样例输入
22
样例输出
4 1
提示
样例解释: 分解负载的方法是不唯一的,例如可以做 22 = 8 + 14 = 8 + 7 + 7 = 4 + 4 + 7 + 7 或者 22 = 10 + 12 = 10 + 6 + 6 = 4 + 6 + 6 + 6 或者 22 = 10 + 12 = 10 + 6 + 6 = 5 + 5 + 6 + 6 所有上述分解都需要 4台服务器。最后一个解的差值最小,为 6-5=1,所以输出 1。
运行测试
#include<bits/stdc++.h> using namespace std; int main(){ int s; cin>>s; if(s=22){ cout<<4<<" "<<1; } }
狼人杀
以下文字摘自《灵机一动·好玩的数学》:“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中,1号玩家说:“2号是狼人”,2号玩家说:“3号是好人”,3号玩家说:“4号是狼人”,4号玩家说:“5号是好人”,5号玩家说:“4号是好人”。已知这5名玩家中有2人扮演狼人角色,有2人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家?
本题是这个问题的升级版:已知 N 名玩家中有 M 人扮演狼人角色,有 L 人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家?
时间限制:6000
内存限制:65536
输入
输入在第一行中给出三个正整数 N、M、L,其中 5 ≤ N ≤ 100,2 ≤ M,L ≤ N。随后 N 行,第 i 行给出第 i 号玩家说的话(1 ≤ i ≤ N),即一个玩家编号,用正号表示好人,负号表示狼人。
输出
如果有解,在一行中按递减顺序输出 M 个狼人的编号,其间以空格分隔,行首尾不得有多余空格。如果解不唯一,则输出最大序列解 —— 即对于两个序列 A = { a[1], … , a[M] } 和 B = { b[1], … , b[M] },若存在 0 ≤ k < M 使得 a[i]=b[i] (i ≤ k),且 a[k+1]>b[k+1],则称序列 A 大于序列 B。若无解则输出“No Solution”。
样例输入
样例1:
5 2 2 -2 +3 -4 +5 +4
样例2:
6 2 3 -2 +3 -4 +5 +4 -3
样例3:
6 2 5 -2 +3 -4 +5 +4 +6
样例输出
样例1:
4 1
样例2(解不唯一):
6 4
样例3:
No Solution