1、链表分组
第一题直接模拟即可，不贴代码了，
超时的估计是在存链表的时候每次都遍历到链表结尾再存，这样肯定超时。
其实就是考了一个翻转链表的套路，每次存的时候存链表尾，然后在最后输出的时候每个依次翻转一次链表就完事了。
2、魔法球
贪心排序
直接对魔法球进行从大到小贪心排序，从头到尾消除即可。
超时的话估计是每消除一个魔法球，就遍历剩余的球加分，这样n平方复杂度肯定超时。
其实思路就是用一个变量保存前面消除魔法球的增量，每消除一个魔方球时，就把当前魔法球和增量都加入ans，然后增量在增加就好了。
坑点：每次加的时候记得取余
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin >> T;
int mod = 1000000007;
for (int i = 0; i < T; i++) {
int n;
cin >> n;
vector<int> vec;
for (int j = 0; j < n; j++) {
int tmp;
cin >> tmp;
vec.push_back(tmp);
}
sort(vec.begin(), vec.end(), greater<int>());
long long ans = 0;
long long sum = 0;
for (int k = 0; k < n; k++) {
ans += (sum + vec[k]);
ans %= mod;
sum += (sum + vec[k]);
sum %= mod;
}
cout << ans << endl;
}
} 很直观的思路，奇数和偶数分组排序，奇数遍历一次，偶数遍历一次，
遍历的时候，双指针首尾，首尾相加小于载重，船+1，left++， right--，大于载重，right--，船+1，因为这个最重的人只能一个人坐船了。
我还用了二分，看别人解法应该不用二分，上述的思路直接得出最小值了，我还是贴我的二分代码出来了，没超时
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool findNum(vector<int>& vec1, vector<int>& vec2, int num, int w) {
int count = 0;
int left = 0, right = vec1.size() - 1;
while (left <= right) {
if (left == right) {
count++;
break;
}
else {
int v = vec1[left] + vec1[right];
if (v <= w) {
count++;
left++;
right--;
}
else if (v > w) {
count++;
right--;
}
}
}
if (count > num) {
return false;
}
left = 0, right = vec2.size() - 1;
while (left <= right) {
if (left == right) {
count++;
break;
}
else {
int v = vec2[left] + vec2[right];
if (v <= w) {
count++;
left++;
right--;
}
else if (v > w) {
count++;
right--;
}
}
}
return count <= num;
}
int main() {
int T;
cin >> T;
while (T > 0) {
T--;
int n, w;
cin >> n >> w;
vector<int> vec1;
vector<int> vec2;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
if (tmp % 2) {
vec1.emplace_back(tmp);
}
else {
vec2.emplace_back(tmp);
}
}
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
int left = 1, right = n, pos = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (findNum(vec1, vec2, mid, w)) {
pos = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
cout << pos << endl;
}
return 0;
}
4、求字符串
维护一个严格单调递减栈即可，但维护弹栈的时候需要考虑后面的字符还够不够选
#include <iostream>
#include<stack>
#include<string>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
stack<char> stk;
for (int i = 0; i < n; i++) {
//维护一个严格单调递减栈
//如果当前字符比栈顶字符大，普通单调递减栈就是直接弹出，直接栈为空，或者遇到栈顶字符比当前字符大
//但是在该题中需要考虑，如果把栈的字符弹出了，后续字符还够不够选择，所以需要判断一下，也就是n - i > k的作用
while (!stk.empty() && stk.top() < s[i] && n - i > k) {
stk.pop();
//弹出一次，可选字符k++
k++;
}
//如果k小于等于0，不能加字符了
if (k <= 0) {
continue;
}
//当前字符小于或等于栈顶字符，或者栈空
stk.push(s[i]);
k--;
}
//逆序输出即可
string ans = "";
while (!stk.empty()) {
ans += stk.top();
stk.pop();
}
reverse(ans.begin(), ans.end());
cout << ans << endl;
} 5、涂方块 完全不会，暴力也不会，求思路，私聊回复都行。
全部评论
(3) 回帖