upc 个人训练赛第十场：组装玩具+河床（二分+最长不下降子序列）

问题 A: 金子数

题目描述
某地区有 n 条（编号依次为 1 到 n）互不交叉的道路，每条道路上都有 m 个数字，其中 能被 8 整除的数称为金子数，这个数字表示其重量。
如下表是 3 条道路，每条道路中有 5 个数的一种可能情况。

小华想在 n 条道路中走一条金子重量之和最大的道路，请编程帮他找出这条道路吧.

输入
输入共 n+1 行。
第 1 行两个整数 n 和 m，表示总共有 n 条道路，每条道路上有 m 个数。 接下来 n 行，每行 m 个正整数。

输出
输出共 1 行。 一个整数，表示金子重量之和最大的道路编号。
样例输入 Copy
3 5
13 24 17 8 23
1 2 3 4 5
16 2 16 4 8
样例输出 Copy
3
提示
输入的样例中，金子重量之和最大的道路编号为 3，具体情况见问题描述。

30%的测试点输入数据保证 1≤n≤10，1≤m≤100，路上的每个数都不超过 100。
100%的测试点输入数据保证 1≤n≤100，1≤m≤10000，路上的每个数都不超过 100000。 所有的测试点输入数据保证金子重量之和最大的道路只有一条，且肯定存在。

思路：
定义一个数组存储符合条件的数值即可

int m,n,sum,maxx;
int a[105][10005];
int b[105];
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++)memset(a[i],0,sizeof(a[i]));memset(b,0,sizeof(b));for(int i=0;i<n;i++)for(itn j=0;j<m;j++)scanf("%d",&a[i][j]);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]%8 == 0)b[i] += a[i][j];}}maxx = b[0];for(int i=1;i<n;i++){if(maxx < b[i]){maxx = b[i];}}for(int i=0;i<n;i++){if(max == b[i])printf("%d",i+1);}return 0;
}

问题 B: 扑克牌游戏

题目描述
扑克牌有 13 种代表不同点数的牌（不考虑花色），如下图所示，从左到右依次为“A”， “2”，“3”，“4”，…… ，“10”，“J”，“Q”，“K”。

小华正在玩一个扑克牌的游戏，在这个游戏中，每种点数的牌都有一个分数（不一定 跟点数相同）。现在小华手上已经有 n 张扑克牌，他还可以挑选 m 张扑克牌，使得 n+m 张 扑克牌的总分数最大。我们假定每种点数的扑克牌有无穷多张。
请编程计算小华在游戏中可以最多获得多少分？

输入
输入共 3 行。
第 1 行 13 个整数，依次表示每种点数的牌所代表的分数。
第 2 行两个整数 n 和 m，表示小华已经有 n 张扑克牌，还可以挑选 m 张扑克牌。
第 3 行输入表示小华手上已经有的 n 张扑克牌的情况，输入的两张扑克牌信息之间没有 空格分隔。

输出
输出共1行。 输出一个整数，表示小华在游戏中可以获得的最大分数。注意：小华选牌的方案可能不唯一，但只要总分数最大即可，不需要输出选牌的方案。
样例输入 Copy
1 3 1 1 1 1 2 3 4 1 3 0 1
3 2
234
样例输出 Copy
13
提示
小华原来手上有 3 张牌，分别为“2”，“3”，“4”，对应的分数之和为 3+1+1=5，他可以 再挑选 2 张扑克牌，都是点数为“9”的扑克牌，这 2 张牌的分数之和为 4+4=8，所以小华的总得分为 13 分。

50%的测试点输入数据保证小华手上已经有的牌中不会出现“A”、“10”、“J”、“Q”、“K” 这 5 种点数的牌。
80%的测试点输入数据保证小华手上已经有的牌中不会出现“10”这种点数的牌。
100%的测试点输入数据保证 1≤n≤100，0≤m≤100，0≤每种点数的牌所代表的分数≤1000。

思路：
这个输入的牌之间没有空格，所以需要整体输入，一共有n张牌，每次循环找就可以了

string s;
int n,m,maxx,sum,ans;
int a[15],b[105];
int main()
{a[0] = 0;maxx = -1;for(int i=1;i<=13;i++){cin >> a[i];if(a[i] > maxx)//先找出最大值 maxx = a[i];}cin >> n >> m;cin >> s;for(int i=0;i<n;i++){if(s[i] >= '2' && s[i] <= '9')sum += a[s[i]-'0'];if(s[i] == 'A')	sum += a[1];if(s[i] == 'J') sum += a[11];if(s[i] == 'Q')	sum += a[12];if(s[i] == 'K')	sum += a[13];if(s[i] == '1' && s[i+1] == '0'){sum += a[10];n++;}}ans = sum+m*maxx;cout << ans << endl;return 0;
}

问题 C: 垃圾装袋

题目描述
某城市环卫部门需要对分布在城市中不同地点的 n 堆（编号为 1 到 n）垃圾进行装袋处 理。现在有 m 个（编号为 1 到 m）垃圾袋可以使用。

一个容量为 v 的垃圾袋能装入不超过容量为 v 的垃圾，一堆垃圾要求只能用一个垃圾 袋来装，一个垃圾袋也只能用来装一堆垃圾（即一个垃圾袋不能在两个地方装垃圾）。一个 垃圾袋的价格是由垃圾袋的容量来决定，容量为 v 的垃圾袋价格为 v。

请编程帮环卫部门计算要将 n 堆垃圾全部装袋，用掉的垃圾袋最少值多少钱？

输入
输入共 3 行。
第 1 行两个正整数 n 和 m，表示需要处理 n 堆垃圾，现在有 m 个垃圾袋。 第 2 行 n 个整数，依次表示每堆垃圾的容量。
第 3 行 m 个整数，依次表示每个垃圾袋的容量。

输出
输出共 1 行。 输出一个整数，如果能将所有的垃圾装入已有的袋子，则输出用掉的垃圾袋最少值多少钱？如果无法将所有的垃圾装入 m 个袋子，则输出“-1”。
样例输入 Copy
3 4
3 6 4
4 5 7 3
样例输出 Copy
14
提示
有3堆垃圾，4个袋子，第1堆容量为3的垃圾用第4个容量为3的袋子装，第2堆容量为6的垃圾用第3个容量为7的袋子装，第3堆容量为4的垃圾用第1个容量为4的袋子 装，所以用掉的垃圾袋最少值3+7+4=14。

30%的测试点输入数据保证1≤n，m≤1000
70%的测试点输入数据保证1≤n，m≤10000
100%的测试点输入数据保证1≤n，m≤50000，每个垃圾袋的容量和每处垃圾的容量 不超过10000。

思路：
for循环找比垃圾容量大的袋子，找到就更新答案，并且让这个袋子等于零结束本次循环，最后查找等于零的袋子，如果袋子数量与垃圾堆的数量不相等，就证明无法将所有的垃圾装完

int n,m,ans,cnt;
int a[maxn],b[maxn];
int main()
{cin >> n >> m;for(int i=1;i<=n;i++)    cin >> a[i];for(int j=1;j<=m;j++)    cin >> b[j];sort(b+1,b+1+m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(b[j] >= a[i]){ans += b[j];b[j] = 0;break;}}}for(int i=1;i<=m;i++)if(b[i] == 0)   cnt++;if(cnt != n)    printf("-1\n");else    cout << ans << endl;return 0;
}

问题 D: 组装玩具

题目描述
小华打算用 n 种（编号为 1 到 n）材料组装玩具。其中第 i 种材料的数量为 Xi 个。组装一个玩具需要第 i 种材料 Yi 个。小华另外有 m 个万能材料，每个万能材料可以作为 n 种材料中的任意一个材料使用。

请编程计算小华最多可以组装多少个玩具？

输入
输入共3行。
第1行两个整数n和m，分别表示小华有n种材料和m个万能材料。第2行n个正整数，其中第i个整数Xi表示小华第i种材料有Xi个。
第3行n个正整数，其中第i个整数Yi表示小华组装一个玩具需要第i种材料Yi个。

输出
输出共 1 行。
一个整数，表示小华最多可以组装多少个玩具。

样例输入 Copy
1 1
1
1
样例输出 Copy
2
提示
输入中小华只有1个编号为1的材料，另外还有1个万能材料。组装一个玩具需要编号为1的材料1个。所以可以用1个编号为1的材料和1个万能材料分别组装1个玩具，共可以组装2个玩具。
50%的测试点输入数据保证1≤n≤1000, 1≤m≤104，1≤Xi, Yi≤104。
100%的测试点输入数据保证1≤n≤100000, 1≤m≤109，1≤Xi, Yi≤109。

思路：
这个题呢，是听了dalao的想法之后做出来的，虽然没有单调性，但是组装玩具没有先后之分，而且数据范围又很大，所以完全可以直接二分去寻找这个答案

ll n,m;
struct node
{ll x,y,z;
}a[maxn];ll check(ll k,ll m)
{for(int i=1;i<=n;i++){if(a[i].z < k)//当前可以组装的玩具比check值小，需要万能材料 m -= a[i].y*k-a[i].x;if(m < 0)	return 0;//万能材料不够用，说明当前情况不符合 }return 1;
}int main()
{cin >> n >> m;for(int i=1;i<=n;i++)	cin >> a[i].x;for(int i=1;i<=n;i++)	cin >> a[i].y;for(int i=1;i<=n;i++)	a[i].z = a[i].x/a[i].y;ll l = 0,r = 10*1e9;while(l < r){ll mid = (l+r) >> 1;if(check(mid,m))	l = mid+1;//当前情况符合了，说明还可以组装更多的玩具，扩大范围else	r = mid;}printf("%lld\n",l-1);return 0;
}

问题 E: 河床

题目描述
小明是一个地理学家，经常要对一段河流进行测量分析。他从上游开始向下游方向等距离地选择了N个点测量水位深度。得到一组数据d1,d2,……,dn，回到实验室后数据分析员根据需要对数据进行分析，发掘隐藏在数据背后的规律。最近，小明发现某种水文现象与河床地势有关，于是他指示分析员要找出一段河流中最大高低起伏差不超过K(k<=100)的最长的一段。这看似一个复杂的问题，由于任务紧急，分析员求助于你，并告诉你小明的所有数据，数据都精确到个位。
输入
包含2行，第一行是整数N和k，分别表示测量点的个数和博士要求的最大水深差(也就是河床地势差)。第二行有N个整数，表示从上游开始一次得到的水位深度为di。
输出
只有一行，是正数M，表示最长一段起伏不超过K的河流长度，用测量点个数表示。
样例输入 Copy
6 2
5 3 2 2 4 5
样例输出 Copy
4

思路：
其实说白了就是一个寻找最长不下降子序列
每次寻找更新最大值即可

itn n,k,tmp,sum,minn,maxx;
int a[maxn];
int main()
{cin >> n >> k;for(itn i=0;i<n;i++)	cin >> a[i];sum = 1;for(itn i=0;i<n;i++){maxx = a[i];minn = a[i];tmp = 1;for(itn j=i+1;j<n;j++){if(a[j] > maxx)	maxx = a[j];if(a[j] < minn)	minn = a[j];if(maxx - minn > k)	break;//一旦这两个数据的差大于k，一定不是当前序列else{tmp++;if(tmp > sum)	sum = tmp;}}}cout << sum << endl;return 0;
}

问题 F: 最长链

题目描述
现给出一棵N个结点二叉树，问这棵二叉树中最长链的长度为多少，保证了1号结点为二叉树的根。
输入
第1行为包含了一个正整数N，为这棵二叉树的结点数，结点标号由1至N。
接下来N行，这N行中的第i行包含两个正整数l[i], r[i]，表示了结点i的左儿子与右儿子编号。如果l[i]为0，表示结点i没有左儿子，同样地，如果r[i]为0则表示没有右儿子。
输出
包括1个正整数，为这棵二叉树的最长链长度。
样例输入 Copy
6
2 3
4 5
0 6
0 0
0 0
0 0
样例输出 Copy
4
提示
样例解释
4-2-1-3-6为这棵二叉树中的一条最长链。
对于100%的数据，有N≤100000，且保证了树的深度不超过32768。

思路：
两次dfs
第一次从任意一个点搜到最远点
再从这个最远点搜到另一个最远点

/**
从任意一点搜到最远点
再从这一点开始搜
搜到最远点
一定是最长链 
**/
int n,ans;
int l[maxn],r[maxn],d[maxn];
void dfs(int k)
{if(!l[k] && !r[k]){d[k] = 1;	return ;}if(l[k])	dfs(l[k]);if(r[k])	dfs(r[k]);ans = max(ans,d[l[k]]+d[r[k]]);d[k] = max(d[l[k]],d[r[k]])+1;
}int main()
{cin >> n;for(int i=1;i<=n;i++)cin >> l[i] >> r[i];dfs(1);cout << ans << endl;return 0;
}int a[10]; 
int main()
{srand(time(0));for(itn i=0;i<10;i++){a[i] = rand() % (40)+1;cout << a[i] << endl;}return 0;
}