问题描述
　　在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

C++ 构建二维动态数组

1
2
3
4
5
6

int **p;
p = new int*[10];    //注意，int*[10]表示一个有10个元素的指针数组
for (int i = 0; i < 10; ++i)
{
    p[i] = new int[5];
}

定义：

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。
　　钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。
　　每次取钥匙的时候，老师们都会找到自己所需要的钥匙将其取走，而不会移动其他钥匙。每次还钥匙的时候，还钥匙的老师会找到最左边的空的挂钩，将钥匙挂在这个挂钩上。如果有多位老师还钥匙，则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。
　　今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课，给出每位老师所需要的钥匙、开始上课的时间和上课的时长，假设下课时间就是还钥匙时间，请问最终钥匙盒里面钥匙的顺序是怎样的？

C++ string append()添加文本

使用append()添加文本常用方法:

array 排序

声明和初始化方法：
想使用string首先要在头文件当中加入< string >
声明方式也很简单

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:

Input: “19:34”

Output: “19:39”

Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39,
which occurs 5 minutes later.

It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: “23:59”

Output: “22:22”

Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22.
It may be assumed that the returned time is next day’s time since it is smaller
than the input time numerically.

法一 暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include<iostream>
#include<algorithm>
#include<string>
#include<set>
using namespace std;
string nextCloseTime(string time)
{
	//!!
	set<char> t(time.begin(),time.end());
	int hour=stoi(time.substr(0,2));
	int min=stoi(time.substr(3,2));
	char str[5];
	while(1){
		min++;
		if(min==60){
			min=0;
			hour=(hour+1)%24;
		}
		sprintf(str,"%02d:%02d",hour,min);
		set<char> s(str,str+sizeof(str));
		//比较是排好序的两个序列 
		if(includes(t.begin(),t.end(),s.begin(),s.end())) break;
		
	}
	string ans=(string)str;
	return ans;
}
int main(void)
{
string p="19:34";
string ans=nextCloseTime(p);
cout<<ans;
}

法二 dfs

用best表示与当前时间相差的分钟数 维护best

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#define INT_MAX 0xffff
using namespace std;

void dfs(int depth,int &best,int curr[],int digits[],int &ans){

	if(depth==4){
		if(curr[0]*10+curr[1]>24) return;
		if(curr[2]*10+curr[3]>59) return;
		int curtime=(curr[0]*10+curr[1])*60+curr[2]*10+curr[3];
		int pastime=(digits[0]*10+digits[1])*60+digits[2]*10+digits[3];
		int tt=(curtime-pastime+24*60)%(24*60);
		if(curtime==pastime) tt=24*60;
		if(tt<best) 
		{
			best=tt;			
		    ans=curtime;		  
		}	
	  return;
	}
    else{
	for(int i=0;i<4;i++){
	curr[depth]=digits[i];
	dfs(depth+1,best,curr,digits,ans); 
	}
	
}
}
string nextCloseTime(string time)
{

int hour=(int)stoi(time.substr(0,2));
int min=(int)stoi(time.substr(3,2));
int digits[4]={hour/10,hour%10,min/10,min%10};
int best=INT_MAX;
int curr[5];
int dep=0;
int ans;
dfs(dep,best,curr,digits,ans);
char buff[5];
sprintf(buff, "%02d:%02d", ans/60, ans%60);
return (string)buff;
}
int main(void)
{
string p="23:59";
string ans=nextCloseTime(p);
cout<<ans;
}

参考链接

https://zxi.mytechroad.com/blog/?s=681

std::includes用于判断序列S2是否包含于序列S1，前提是序列S1,S2必须为有序序列（若为无序序列，首先应该通过std::sort使其变为有序序列），返回false（不包含）或者true（包含）。但是该功能并要求序列S2中的元素在序列S1中仍然连续出现，只是用来判断序列S1是否包含S2中的所有元素（不要求连续），并不类似于字符串判断中的子序列函数strstr。判断两个元素是否相等，需要以less和greater为判断依据，因此配合着两个有序序列S1、S2的排序方式（递增或递减），includes算法可以供用户选择less或者greater进行两个元素的大小比较。
若S1、S2为递增数列，includes函数应该以如下方式使用:

给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。

输入格式

输入的第一行包含一个整数n，表示给定数字的个数。

第二行包含n个整数，相邻的整数之间用一个空格分隔，表示所给定的整数。