360笔试(9-26)的笔经
第一题,数学问题
题目大意
有物品要放在箱子里,一个箱子可以用隔板隔成若干个隔间,一个箱子放2个隔板就可以隔成3个隔间,3个隔板可以隔成4个隔间,以此类推,但一个箱子的隔间数不能超过k个,且每个隔间最多放v个物品。现给出物品个数a、隔板个数b以及k和v,求至少需要多少个箱子才能放下所有物品。a、b、k、v均是正整数。
思路
不难得知至少需要need = ceil(a / v)个隔间,问题就转化成至少要多少个箱子才能得到need个隔间,可以反向思考,有s个箱子和b个隔板最多能得到多少个隔间,由于一个箱子最多有k个隔间,因此最多可以有s * k个隔间,但这需要s * (k-1)个隔板,如果隔板个数b少于这个值,也无法得到这么多隔间,考虑到这种情况下(b < s * (k-1)),每少一个隔板就少获得一个隔间,所以这时得到的隔间个数是s * k - (s * (k-1) - b) = s + b个,综上可以得出在有s个箱子和b个隔板的情况下能得到s + min(b, s * (k-1))个隔间,不妨先假设min的取值是b,那么s = need - b,如果此时s * (k-1)确实大于等于b,那么b确实是min函数的取值,所以这个s是正确的,否则min的取值应当是s * (k-1),那么有s * k >= need,此时s的取值为ceil(need / k)。注意本题要循环处理多个用例。
代码(只列出核心函数)
int solve(int a, int b, int k, int v) { int need = (a + v - 1) / v, s = need - b; if (s * (k-1) >= b) return s; else return (need + k - 1) / k; }
第二题,图论问题
题目大意
给出一个带权无向图,没有自环和重边,给出两个节点s和t,求从s到达t的路径中的所有边里,边权最大的边的权至少有多大。保证s与t连通。
用例以n(节点个数)、m(边数)、s、t,然后m行u、v、w(权的大小)给出,比如:
5 6 1 5
1 5 100
1 2 10
2 5 5
1 3 3
3 4 2
4 5 1
选择从1->3->4->5的路径,经过3条w分别为3、2、1的边,因此答案为3。如果选择1->5或1->2->5则最大边权分别为100和10,都比3大。
思路
类似kruskal算法,先按权的大小升序排序,然后每次依次增加一条边,看s与t是否已经连通,如果此时变得连通,返回此边的权。为什么正确呢?因为在加入这条边之前所有权值小于它的边都已加入图中,但仍未使s与t连通,说明答案不可能比其权值w1小,而加入它以后s与t已经连通,那么必定能找到一条从s到t的路径,且路径上的边最大权值不大于w1(因为权值比w1大的边此时还没加入图中),因此w1就是答案。为了快速地判定s与t的连通性,使用并查集。
代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 100005, M = 200005; struct Edge { int u, v, w; bool operator< (Edge const& e) const { return w < e.w;} } es[M]; int n, m, s, t, par[N], rk[N]; //并查集 int find(int x) { return x == par[x] ? x : (par[x] = find(par[x]));} bool same(int x, int y) { return find(x) == find(y);} void unite(int x, int y) { if ((x = find(x)) == (y = find(y))) return; if (rk[x] < rk[y]) { par[x] = y; } else { par[y] = x; if (rk[x] == rk[y]) rk[x]++; } } int solve() { sort(es, es + m);//按权值排序,Edge类已重载operator< for (int i = 0; i < n; i++) par[i] = i;//初始化并查集 for (int i = 0; i < m; i++) { unite(es[i].u, es[i].v);//将这条边加入 if (same(s, t)) return es[i].w;//如果此时s与t连通返回此边的边权。 } return -1; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); s--, t--;//题目给的点编号是1~n,个人习惯从0开始编号,所以自减1,下同。 for (int i = 0; i < m; i++) { scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].w); es[i].u--, es[i].v--; } printf("%d\n", solve()); }#360笔试##笔经##360公司#