3.27学习总结 算法题

自己用c语言做的，不尽如意

后面看了题解，用的是c++，其中string 变量和字符串拼接感觉比c方便好多，可以用更少的代码实现更好的效果，打算之后去学习c++，用c++写算法。

递归，不断输入字符，若遇到[，则输入解压次数k，重新调用函数，将[中的]字符串重复k次，加在总字符串后，遇到]就返回总字符串，否则将字符加在总字符串尾。

#include<iostream>
using namespace std;
string yunqian() {int k;char ch;string s = "", str = "";while (cin >> ch) {if (ch == '[') {cin >> k;str = yunqian();while (k--) {s += str;}}else if (ch == ']') {return s;}else {s += ch;}}return s;
}
int main()
{   string s=yunqian();cout << s;return 0;
}

递推，

对于2*n的墙，当其还剩最后一列没铺时，用发a[n-1]表示，竖着铺2*1的砖即可铺满；

当其还剩最后一列没铺时，用发a[n-1]表示，横着着铺两个2*1的砖即可铺满；

当其还剩最后一列和倒数第二列的一个没铺时，用b[n-2]表示，

可以拆掉一块三单元的砖，使其变成a[n-3];

也可以拆掉一块横向2*1的砖，使其变为b[n-3];

得到公式：

a[i] = a[i - 1] + a[i - 2]d + 2 * b[i - 2];
b[i] = a[i - 1] + b[i - 1];

#include <iostream>
using namespace std;
int a[1000005],b[1000005];
int mod = 10000;
int main()
{int n;cin >> n;a[0] = 1;b[0] = 0;a[1] = 1;b[1] = 1;for (int i = 2; i <= n; i++) {a[i] = ((a[i - 1] + a[i - 2])%mod + 2 * b[i - 2]%mod)%mod;b[i] = (a[i - 1] + b[i - 1])%mod;}cout <<a[n];return 0;
}

水题，用结构体确保可以正确输入序号，为了使等待时间最短，将节水时间按从小到大排序，可得，对于第i个人，等待时间为n-乘以Ti,保留两位小数

#include <iostream>
using namespace std;
struct {int d;int i;
}a[1006],t;
int main()
{int n;double sum = 0;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i].d;a[i].i = i;}for (int i = 1; i <= n - 1; i++) {for (int j = 1+i; j <= n; j++) {if (a[i].d > a[j].d) {t = a[i];a[i] = a[j];a[j] = t;}}}for (int i = 1; i <= n; i++) {sum += (n - i)*a[i].d;}sum /= n;for (int i = 1; i <= n; i++) {cout << a[i].i<<" ";}cout << "\n";printf("%0.2f", sum);return 0;
}

贪心：

从1到n-1遍历循环，若这个盒子和下一个盒子的糖果之和大于x，则 将下个盒子的糖果吃到x颗

之后就可以成功的报错了

需要注意特殊情况，对第一个盒子单独判断，若里面的糖果数量大于x，吃掉其中糖果，直到剩下x颗糖，从二开始循环就可以ac了。

#include <iostream>
using namespace std;
int main()
{int n,x;int a[100005];long long sum = 0;cin >> n;cin >> x;cin >> a[1];if (a[1] > x) {sum += a[1] - x;a[1] = x;}for (int i = 2; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n - 1; i++) {while (a[i] + a[i + 1] > x) {sum += a[i] + a[i + 1] - x;a[i + 1] = x - a[i];}}cout << sum;
}

用结构体数组存储每场比赛的开始时间与结束时间，将数组按照结束时间升序排列。

现在的时间初始为零，从前往后循环数组，若开始时间大于等于现在的时间，则现在的时间等于这场比赛的结束时间，参加的比赛加一。

#include <iostream>
#include <algorithm>
using namespace std;
int n, t, num;
struct node{int l;int r;
}a[1000006];
bool cmp(node a, node b) {return a.r < b.r;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i].l>> a[i].r;}sort(a+1, a + n+1,cmp);for (int i = 1; i <= n; i++) {if (a[i].l >= t) {t = a[i].r;num++;}}cout << num;return 0;}