9.17百度C++编程题
1.数学题 m*a+n*b>=n*m-k,求a+b最小值,题目说了不等式右边大于零,a和b非负。为了让a+b越小,所以让m,n中的较大值的乘积项越大越好。
#include<bits/stdc++.h> using namespace std; int main() { long long n, m,k; scanf("%lld %lld %lld", &n, &m, &k); long long sum = n*m - k; long long res; if (m > n) { res = sum / m + sum % m; } else { res = sum / n + sum % n; } printf("%lld", res); }
2.安排任务,给出各个任务的所需时间和deadline,看是否有任务会超时,模拟一下
#include<bits/stdc++.h> using namespace std; bool cmp(pair<int, int> a, pair<int, int>b) { if (a.second != b.second)return a.second < b.second; return a.first < b.first; } int main() { int t,n, a, b; scanf("%d", &t); while (t--) { scanf("%d", &n); vector<pair<int, int>> v; for (int i = 0; i < n; i++) { scanf("%d%d", &a, &b); v.push_back({ a,b }); } sort(v.begin(), v.end(), cmp); int cur = 0; bool flag = true; for (auto it : v) { cur += it.first; if (cur > it.second) { flag = false; break; } } printf(flag ? "Yes\n" : "No\n"); } return 0; }3.二人博弈。用dfs遍历了两次,找到两人能访问的中间结点,和各自一边的节点。中间结点数为偶数,两人平分;为奇数,牛牛多取一个。牛牛先手,胜利条件是牛牛能取的点要比牛妹多
#include<bits/stdc++.h> using namespace std; int t, n, a, b; vector<int> v[100005]; bool vis1[100005], vis2[100005]; void dfs1(int index) { if (index == n)return; vis1[index] = true; for (int i = 0; i < v[index].size(); i++) { if(vis1[v[index][i]]==false)dfs1(v[index][i]); } } void dfs2(int index) { if (index == 1)return; vis2[index] = true; for (int i = 0; i < v[index].size(); i++) { if (vis2[v[index][i]] == false) dfs2(v[index][i]); } } int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < 100005; i++) { v[i].clear(); } fill(vis1, vis1 + 100005, 0); fill(vis2, vis2 + 100005, 0); for (int i = 0; i < n-1; i++) { scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } int res1 = 0, res2 = 0; dfs1(1); dfs2(n); for (int i = 2; i < n; i++) { if (vis1[i]) { if (vis2[i]) { res1++; res2++; }else { res1 += 2; } }else { if (vis1[2]) { res2 += 2; } } } res1 = res1 / 2 + res1 % 2) ; res2 = res2 / 2; if (res1 > res2)printf("niuniu\n"); else printf("niumei\n"); } return 0; }