牛客刷题记录01

除2！

目录

除2！

题目描述：

​编辑 题目解析：

代码实现：

数组中两个字符串的最小距离__牛客网

题目描述：

题目解析：

代码实现：

除2！

题目描述：

给一个数组，一共有 n n\\ n 个数。
你能进行最多 k k\\ k 次操作。每次操作可以进行以下步骤：

• 选择数组中的一个偶数 aia_iai​，将其变成 ai/2a_i/2ai​/2 。

现在你进行不超过 k k\\ k 次操作后，让数组中所有数之和尽可能小。请输出这个最小的和。

 题目解析：

        不难想到，每次对最大的偶数除2即可，我们可以使用堆来获取每次更新后最大的偶数。

代码实现：

#include #include using namespace std;long long Continuously_divide_by_2(){priority_queue q;int n, k;cin >> n >> k;long long ans = 0;for (int i = 0; i > t;ans += t;if (t % 2 == 0) q.push(t);}int m = 0;while (m < k && !q.empty()){int t = q.top();q.pop();t /= 2;ans -= t;if(t % 2 == 0)q.push(t); m++;}return ans;}int main(){ cout << Continuously_divide_by_2() << endl; return 0;}

 这里的结果需要用long long保存。

数组中两个字符串的最小距离__牛客网

题目描述：

给定一个字符串数组strs，再给定两个字符串str1和str2，返回在strs中str1和str2的最小距离，如果str1或str2为null，或不在strs中，返回-1。

题目解析：

• 这道题我们甚至不需要用一个字符串数组来保存这些字符串；
• 我们只需要一个pos变量来记录最新出现的目标字符串的位置，和一个tmpstr变量来记录出现的是哪个目标字符串（因为有两个）；
• 当出现的目标字符串于tmpstr不一样的时候，就可以尝试更新距离，只要出现目标字符串就更新pos。 

代码实现：

#include using namespace std; int Minimum_distance() { int n = 0; string str1, str2, strs, strt; int pos = 0; cin >> n; cin >> str1 >> str2; int ans = n + 1; for (int i = 0; i > strs; if (strs == str1) { if (strt.empty() || strt == str1) {} else { ans = min(ans, i - pos); } pos = i; strt = str1; } else if (strs == str2) { if (strt.empty() || strt == str2) {} else { ans = min(ans, i - pos); } pos = i; strt = str2; } } if (ans == n + 1) return -1; else return ans;} int main() { cout << Minimum_distance(); return 0;}