【LittleXi】拼多多后端8.11解题报告
极限ak，开题顺序3421成谜
A、旅行计划
题意：
给定n个旅行计划，每个旅行计划完成的时间只能是xi,xi+d,xi+2d,...，并且每天最多只能完成一个旅游，求最小时间
题解：
可以考虑维护当前的天数result
如果result小于当前旅行计划开始的天数，那么result = day_i
否则求最小的b使得day_i + b * d > result
注意坑就是求b的时候，也可以day_i + b * d = result ， 此时要b++
// 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll n;
cin>>n;
vector<vector<ll>> data(n,vector<ll>(3));
for(ll i= 0;i<n;i++){
cin>>data[i][0]>>data[i][1]>>data[i][2];
}
sort(data.begin(),data.end());
ll result = 1;
for(ll i =0;i<n;i++){
vector<ll> current = data[i];
if(result < current[1]){
result = current[1];
}
else{
ll day = current[1];
ll dis = result - day;
ll b = dis/current[2] + (dis%current[2] > 0);
if(day + b * current[2]==result) b ++;
result = day + b * current[2];
}
}
cout<<result<<endl;
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
solve();
}
B、多多的作业
题意：
给定n个作业，作业有开始时间和需要的时间，求最小总作业消耗时间，单个作业消耗时间是作业完成时间减去作业开始时间
题解：
可以考虑使用优先队列进行贪心， 每次获取作业的时候，对于前面那个时间片，我们优先让消耗时间小的作业被计算
代码：
// 2
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll n;
cin>>n;
vector<pair<ll,ll>> vp(n);
for(ll i =0;i<n;i++) cin>>vp[i].first>>vp[i].second;
priority_queue<ll,vector<ll>,greater<ll>> pq;
ll t = 1 , ans = 0;
pq.push(vp[0].second);
for(ll i =1;i<n;i++){
ll d = vp[i].first - vp[i-1].first;
while(pq.size()&&d){
auto x = pq.top();pq.pop();
ll dis = min(x,d);
ans += dis * (pq.size() + 1);
x -= dis ; d -= dis;
if(x) pq.push(x);
}
pq.push(vp[i].second);
}
while(pq.size()){
ll x = pq.top();pq.pop();
ans += x * (pq.size() + 1);
}
cout<<ans;
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
solve();
}
C、玫瑰和牡丹
题意：
给一个01串，你可以最多选择一个区间进行反转，0->1 , 1->0 ,求最终abs(cnt[0]-cnt[1])的可能数
题解：
我们可以这样考虑，每次延长我们的[l,r]区间一次，cnt[0] - cnt[1] 要么+1，要么-1，所以我们可以求一个区间，使得cnt[0] - cnt[1] 最大或者最小，这个可以使用前缀和解决，那么对于最大的cnt[0] - cnt[1] ， 一定可以每次+2到达，所以沿途的数字都可以到达
代码：
// 3
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
int n ;cin>>n;
vector<int> a(n);
for(int&x:a) cin>>x;
for(int&x:a) if(x==0) x = -1;
int prmi = 0 , prmx = 0;
int pr = 0;
int mx = 0 , mi = 0;
for(int i = 0;i<n;i++){
pr += a[i];
mx = max(mx,pr-prmi);
mi = min(mi,pr-prmx);
prmx = max(prmx,pr);
prmi = min(prmi,pr);
}
set<int> se;
int sm = accumulate(a.begin(),a.end(),0);
for(int i = sm - 2*mx ; i <= sm -2*mi;i+=2){
se.insert(abs(i));
}
cout<<se.size();
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
solve();
}
D、哈希表
难度：区域赛铜牌题目，一股ACM味儿
题意：
哈希函数为f = x % n , 给定一个插入完成的哈希表，要求还原插入顺序，如果多个可能，还原字典序最小的
题解：
很容易想到使用拓扑排序，对于从i位置跳到j位置的数字， 将[i,j-1]的所有点连向j，然后进行拓扑排序+贪心就行，时间复杂度n^2 , 不行
可以考虑优化，删除一个数字之后，一定是右边最靠近这个数字可能被选，可以压进优先队列中，查找右边那个数字可以考虑使用树状数组+二分，时间复杂度nlg^2n
代码：
// 4
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//坐标从0开始直接用的树状数组
template <typename T>
class Fenwick
{
private:
int n;
vector<T> c;
int lowbits(int x){
return (-x) & x;
}
int pre_sum(int i){
int re = 0;
for (; i > 0; i -= lowbits(i))
re += c[i];
return re;
}
public:
explicit Fenwick<T>(vector<T> v){
this->n = v.size();
this->c = vector<T>(n+1,0);
for(int i=0;i<n;i++)
add(i,v[i]);
};
void add(int i, int val){
++i;
for (;i<=n; i += lowbits(i))
c[i] += val;
}
int range_sum(int i,int j){
++i;++j;
return pre_sum(j) - pre_sum(i - 1);
}
};
void solve(){
int n;cin>>n;
vector<int> a(n);
for(int &x:a) cin>>x;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
map<int,int> mp;
for(int i =0;i<n;i++){
if(a[i]==-1) a[i] = 0;
else if(a[i]%n==i){
pq.push({a[i],i});
mp[a[i]] = 1;
}
}
for(int i =0 ;i < n;i++) a.push_back(a[i]);
vector<int> b = a;
for(int&x:b) if(x) x = 1;
Fenwick<int> fw(b);
vector<int> ans;
while(pq.size()){
auto p = pq.top();pq.pop();
int x = p.first , pos = p.second;
ans.push_back(x);
fw.add(pos,-1);fw.add(pos+n,-1);
int l = pos , r = 2*n;
while(l+1!=r){
int m = l+r>>1;
if(fw.range_sum(pos,m)==0) l = m;
else r = m;
}
l++;
if(l<2*n&&fw.range_sum(pos,l)==1){
if(mp[a[l]]) continue;
int lp = a[l]%n;
if(lp > l) l+=n;
if(fw.range_sum(lp, l - 1)==0){
mp[a[l]] = 1;
if(l >= n ) l -= n;
pq.push({a[l],l});
}
}
}
for(int x:ans) cout<<x<<" ";
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
solve();
}
❤关注LittleXi ,谢谢喵， ACM金牌，持续更新更多题解❤
也可以提供大厂算法辅导喵
