第 100 场双周赛-爱代码爱编程
第 100 场双周赛
这场偏简单,前面有点思维。
赛时源代码,没任何优化。
Q1 思维
当时刚洗完澡,还蒙的。写了半天判断,越来越乱,后来干脆就暴力了。暴力还wa2.
class Solution {
public:
int distMoney(int money, int children) {
if (money < children) return -1;
if (money == children) return 0;
money -= children;
vector<int> res(50, 0);
for (int i = 0; i < children; i++) res[i] += 1;
int i = 0;
while (money >= 7) {
money -= 7;
res[i++] += 7;
if(i>=children) {
i=children-1;
}
}
if (money > 0) res[i] += money;
int cnt = 0;
for (int j = 0; j < children; j++) {
if (res[j] == 8) cnt++;
}
if(res[i]==4&&i==children-1) return max(0,cnt-1);
return cnt;
}
};
Q2 思维+贪心
排序后的答案和原数组一样。
贪心,每个数都找第一个比它大的。
class Solution {
public:
int maximizeGreatness(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int i=0;
for(auto&x:nums){
if(x>nums[i]){
i+=1;
}
}
return i;
}
};
Q3 优先队列
每次都找最小的数,同时用一个数组标记。显然是优先队列,最多出队 n 次。
class Solution {
public:
long long findScore(vector<int>& nums) {
priority_queue<pair<int, int>,vector<pair<int,int> >,greater<pair<int,int>> >q;
for (int i = 0; i < nums.size(); i++) {
q.push({nums[i], i});
}
long long ans = 0;
vector<int> vis(nums.size(), 0);
while (!q.empty()) {
auto p = q.top();
q.pop();
int val = p.first;
int idx = p.second;
if (!vis[idx]) {
ans += val, vis[idx] = 1;
// printf("%d \n",val);
if (idx - 1 >= 0) vis[idx - 1] = 1;
if (idx + 1 < nums.size()) vis[idx + 1] = 1;
}
}
cout << ans << endl;
return ans;
}
};
Q4 二分
经典了,只是计算的方式略微有一点点新。
class Solution {
public:
typedef long long ll;
long long repairCars(vector<int>& ranks, int cars) {
int n = ranks.size();
ll l=0,r=1e18;
while(l<r){
ll mid = (l+r)>>1;
ll cnt = 0;
for(int i=0;i<n;i++){
cnt += (int)sqrt(mid/ranks[i]);
}
if(cnt>=cars) r = mid;
else l = mid+1;
}
return l;
}
};
总结:前面两题思维wa的有点多,说明确实自己没思维。