OJ – 第18页 – liuchuo

1006. Sign In and Sign Out (25)-PAT甲级真题

At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

Input Specification:

Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:

ID_number Sign_in_time Sign_out_time

where times are given in the format HH:MM:SS, and ID number is a string with no more than 15 characters.

Output Specification:

For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.

Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.

Sample Input:

CS301111 15:30:28 17:00:10

SC3021234 08:00:00 11:25:25

CS301133 21:45:00 21:58:40

Sample Output:

SC3021234 CS301133

题目大意：给出n个人的id、sign in时间、sign out时间，求最早进来的人和最早出去的人的ID～

分析：将时间都转换为总秒数，最早和最迟的时间保存在变量minn和maxn中，并同时保存当前最早和最迟的人的ID，最后输出～

#include <iostream>
#include <climits>
using namespace std;
int main() {
    int n, minn = INT_MAX, maxn = INT_MIN;
    scanf("%d", &n);
    string unlocked, locked;
    for(int i = 0; i < n; i++) {
        string t;
        cin >> t;
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int tempIn = h1 * 3600 + m1 * 60 + s1;
        int tempOut = h2 * 3600 + m2 * 60 + s2;
        if (tempIn < minn) {
            minn = tempIn;
            unlocked = t;
        }
        if (tempOut > maxn) {
            maxn = tempOut;
            locked = t;
        }
    }
    cout << unlocked << " " << locked;
    return 0;
}

#include <iostream>

#include <climits>

using namespace std;

int main() {

int n, minn = INT_MAX, maxn = INT_MIN;

scanf("%d", &n);

string unlocked, locked;

for(int i = 0; i < n; i++) {

string t;

cin >> t;

int h1, m1, s1, h2, m2, s2;

scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);

int tempIn = h1 * 3600 + m1 * 60 + s1;

int tempOut = h2 * 3600 + m2 * 60 + s2;

if (tempIn < minn) {

minn = tempIn;

unlocked = t;

}

if (tempOut > maxn) {

maxn = tempOut;

locked = t;

}

cout << unlocked << " " << locked;

return 0;

}

一脸懵比：length() 以及 size_t

刚刚刷 leetcode 的时候又发生了一件灵异事件：

Snip20160420_20

//题目很简单：

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

但是报错了：

Snip20160420_21

奇怪点不在这，在于如果我把两个.length()替换成 int 型的len1和 len2，就 Accepted了。。

就是写成这样就对了：

Snip20160420_22

啊，为什么。。。为什么。。什么都没干啊只是等价替换了啊。。

a82aa4a836975b078e8d_size71_w440_h774

后来机智的我想起，原来在 IDE 里面编程的时候，每次用 .length()会有警告提醒：

Snip20160420_26

size_type。。。

Snip20160420_29

所以说在 unsigned 情况下，如果两个 length()相减，得到的是一个好大好大的值，因为unsingned和unsigned相减得到unsigned的数，也就是如果是负数的话得到的是int的最大值那样的数，但是在转为 int 型之后就会允许相减得到负数，是这样的么。。。验证一下：

Snip20160420_32

啊，我怎么可以这么机智~~(｀･ω･´)

746-160311154339 ~~~~~~~~~~~~

1011. A+B和C (15)-PAT乙级真题

题目描述：

给定区间[-2^31, 2^31]内的3个整数A、B和C，请判断A+B是否大于C。

输入格式：

输入第1行给出正整数T(<=10)，是测试用例的个数。随后给出T组测试用例，每组占一行，顺序给出A、B和C。整数间以空格分隔。输出格式：对每组测试用例，在一行中输出“Case #X: true”如果A+B>C，否则输出“Case #X: false”，其中X是测试用例的编号（从1开始）。

输入样例：

4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647

输出样例：

Case #1: false
Case #2: true
Case #3: true
Case #4: false

分析：使用long long int存储a、b和c，当a + b > c的时候输出true，否则输出false～

#include <iostream>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        long long int a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        printf("Case #%d: %s\n", i + 1, a + b > c ? "true" : "false");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

scanf("%d", &n);

for (int i = 0; i < n; i++) {

long long int a, b, c;

scanf("%lld%lld%lld", &a, &b, &c);

printf("Case #%d: %s\n", i + 1, a + b > c ? "true" : "false");

}

return 0;

}

蓝桥杯历届试题-六角填数（12）

Snip20160318_79
第7题：六角填数（12）
如图所示六角形中，填入1~12的数字。
使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
请通过浏览器提交答案，不要填写多余的内容。

answer：10
标记从上到下从左到右为1~12

#include <iostream>
using namespace std;
int book[13]; //标记1~12有没有被使用过
int a[13]; //标记12个位置所对应的数
int line[6];

void dfs(int x) {
	int i;
	//如果是已经填了数的那个，就直接跳过搜索下一个
	if(x == 1 || x == 2 || x == 12) {
		dfs(x + 1);
		return ;
	}
	//如果12个已经填满了，就判断是否满足每一条线上的都相等
	if(x > 12) {
		line[0] = a[1] + a[3] + a[6] + a[8];
		line[1] = a[1] + a[4] + a[7] + a[11];
		line[2] = a[8] + a[9] + a[10] + a[11];
		line[3] = a[2] + a[3] + a[4] + a[5];
		line[4] = a[2] + a[6] + a[9] + a[12];
		line[5] = a[5] + a[7] + a[10] + a[12];
		//判断是否两两相等，只要一层循环就好了
		//如果不相等，就直接return，说明这种情况不符合
		for(i = 1; i <= 5; i++) {
			if(line[i] != line[i - 1])
				return ;
		}
		//如果都满足，则输出a[6]的值
		cout << a[6] << endl;
		return ;
	}

	//从数字1到数字12，看有没有没填过的数字，没有填过就填入当前空格
	for(i = 1; i <= 12; i++) {
		if(book[i] == 0) {
			book[i] = 1;
			a[x] = i;
			//填入后就填下一个数字
			dfs(x + 1);
			book[i] = 0;
		}
	}
}


int main() {
	//根据题意初始化值
	book[1] = 1;
	book[3] = 1;
	book[8] = 1;
	a[1] = 1;
	a[2] = 8;
	a[12] = 3;

	dfs(1);
	return 0;
}

#include <iostream>

using namespace std;

int book[13]; //标记1~12有没有被使用过

int a[13]; //标记12个位置所对应的数

int line[6];

void dfs(int x) {

int i;

//如果是已经填了数的那个，就直接跳过搜索下一个

if(x == 1 || x == 2 || x == 12) {

dfs(x + 1);

return ;

}

//如果12个已经填满了，就判断是否满足每一条线上的都相等

if(x > 12) {

line[0] = a[1] + a[3] + a[6] + a[8];

line[1] = a[1] + a[4] + a[7] + a[11];

line[2] = a[8] + a[9] + a[10] + a[11];

line[3] = a[2] + a[3] + a[4] + a[5];

line[4] = a[2] + a[6] + a[9] + a[12];

line[5] = a[5] + a[7] + a[10] + a[12];

//判断是否两两相等，只要一层循环就好了

//如果不相等，就直接return，说明这种情况不符合

for(i = 1; i <= 5; i++) {

if(line[i] != line[i - 1])

return ;

}

//如果都满足，则输出a[6]的值

cout << a[6] << endl;

return ;

}

//从数字1到数字12，看有没有没填过的数字，没有填过就填入当前空格

for(i = 1; i <= 12; i++) {

if(book[i] == 0) {

book[i] = 1;

a[x] = i;

//填入后就填下一个数字

dfs(x + 1);

book[i] = 0;

}

int main() {

//根据题意初始化值

book[1] = 1;

book[3] = 1;

book[8] = 1;

a[1] = 1;

a[2] = 8;

a[12] = 3;

dfs(1);

return 0;

}

#论char数组结尾’\0’的必要性#

只想讲个故事。
今天刷题的时候。
发生了一件很坑的事。 Snip20160318_86
啊啊啊 char a明明只有####，怎么多出来后面一串数字。。
百思不得其解。
后来才知道。
忘记了结尾符。
所以输出a的时候。
它找啊找找，找’\0’。
找到了萌萌的string s后面的结尾符。
于是愉快的输出了如图所示的内容。
啊，编译器你真可爱。
心塞啊。。。。
【手动再见-_-||

“memset是计算机中C/C++语言函数。将s所指向的某一块内存中的前n个字节的内容全部设置为ch指定的ASCII值，第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作，其返回值为指向s的指针。”

所以说是我乱用memset函数了呢。。
嗯。。
所以那句话应该这么写：
Snip20160318_88

1055. 集体照 (25)-PAT乙级真题

拍集体照时队形很重要，这里对给定的N个人K排的队形设计排队规则如下：
每排人数为N/K（向下取整），多出来的人全部站在最后一排；
后排所有人的个子都不比前排任何人矮；
每排中最高者站中间（中间位置为m/2+1，其中m为该排人数，除法向下取整）；
每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；
若多人身高相同，则按名字的字典序升序排列。这里保证无重名。
现给定一组拍照人，请编写程序输出他们的队形。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出两个正整数N（<=10000，总人数）和K（<=10，总排数）。随后N行，每行给出一个人的名字（不包含空格、长度不超过8个英文字母）和身高（[30, 300]区间内的整数）。
输出格式：
输出拍照的队形。即K排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方。
输入样例：
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
输出样例：
Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

分析：建立结构体node，里面包含string类型的姓名name和int类型的身高height～将学生的信息输入到node类型的vector数组stu中～然后对stu数组进行排序（cmp函数表示排序规则，如果身高不等，就按照身高从大到小排列；如果身高相等，就按照名字从小到大的字典序排列～）然后用while循环排列每一行，将每一行应该排列的结果的姓名保存在ans数组中～

因为是面对拍照者，后排的人输出在上方，前排输出在下方，每排人数为N/K（向下取整），多出来的人全部站在最后一排，所以第一排输出的应该是包含多出来的人，所以while循环体中，当row == k时，表示当前是在排列第一行，那么这一行的人数m应该等于总人数n减去后面的k列*(k-1)行，即m = n – n / k * (k-1)；如果不是第一行，那么m直接等于n / k；最中间一个学生应该排在m/2的下标位置，即ans[m / 2] = stu[t].name；然后排左边一列，ans数组的下标 j 从m/2-1开始，一直往左j–，而对于stu的下标 i，是从t+1开始，每次隔一个人选取（即i = i+2，因为另一些人的名字是给右边的），每次把stu[i]的name赋值给ans[j–]；排右边的队伍同理，ans数组的下标 j 从m/2 + 1开始，一直往右j++，stu的下标 i，从t+2开始，每次隔一个人选取（i = i+2），每次把stu[i]的name赋值给ans[j++]，然后输出当前已经排好的ans数组～每一次排完一列row-1，直到row等于0时退出循环表示已经排列并输出所有的行～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    string name;
    int height;
};
int cmp(struct node a, struct node b) {
    return a.height != b.height ? a.height > b.height : a.name < b.name;
}
int main() {
    int n, k, m;
    cin >> n >> k;
    vector<node> stu(n);
    for(int i = 0; i < n; i++) {
        cin >> stu[i].name >> stu[i].height;
    }
    sort(stu.begin(), stu.end(), cmp);
    int t = 0, row = k;
    while(row) {
        if(row == k)
            m = n - n / k * (k - 1);
        else
            m = n / k;
        vector<string> ans(m);
        ans[m / 2] = stu[t].name;
        // 左边一列
        int j = m / 2 - 1;
        for(int i = t + 1; i < t + m; i = i + 2)
            ans[j--] = stu[i].name;
        // 右边一列
        j = m / 2 + 1;
        for(int i = t + 2; i < t + m; i = i + 2)
            ans[j++] = stu[i].name;
        // 输出当前排
        cout << ans[0];
        for(int i = 1; i < m; i++)
            cout << " " << ans[i];
        cout << endl;
        t = t + m;
        row--;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

struct node {

string name;

int height;

};

int cmp(struct node a, struct node b) {

return a.height != b.height ? a.height > b.height : a.name < b.name;

}

int main() {

int n, k, m;

cin >> n >> k;

vector<node> stu(n);

for(int i = 0; i < n; i++) {

cin >> stu[i].name >> stu[i].height;

}

sort(stu.begin(), stu.end(), cmp);

int t = 0, row = k;

while(row) {

if(row == k)

m = n - n / k * (k - 1);

else

m = n / k;

vector<string> ans(m);

ans[m / 2] = stu[t].name;

// 左边一列

int j = m / 2 - 1;

for(int i = t + 1; i < t + m; i = i + 2)

ans[j--] = stu[i].name;

// 右边一列

j = m / 2 + 1;

for(int i = t + 2; i < t + m; i = i + 2)

ans[j++] = stu[i].name;

// 输出当前排

cout << ans[0];

for(int i = 1; i < m; i++)

cout << " " << ans[i];

cout << endl;

t = t + m;

row--;

}

return 0;

}