Google KickStart 19 round A 题目解析

[TOC]

github

## 分析

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

$O(RClog(R+C))$

github

## 分析

S : booking_set
for i =0 : q
book_j = argmax(number_of_seat(S))
S = S/{book_j}

$ans1<=number1(p_q),ans2<=number2(p_j),number1(p_j)>=number2(p_j)>=number1(p_q)\ge ans1$ 因此 在序列 1中 $p_j$ 不是瓶颈。同时 $number2(p_i)\ge number1(p_i),\forall i\neq j$ (因为遮挡少了 $p_j$)

ok。这就引出了一个朴素的算法，就是伪代码的做法，不过我们需要确定的是booking 放在最后能够book到多少seat。 这个可以用扫描线 $O(Q)$ 做出来，只有 $Q$ 条线段。

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
#define ms(x,v) memset(x,(v),sizeof(x))

typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TIII;
typedef pair<PII,int> PIII;
const int MAXN = 1e6+10;

int del(map<PII,int>& seg){
int last = 0;
for(auto it = seg.begin(); it != seg.end();){
auto now = it;
const int st = now -> first.first;
const int ed = -now -> first.second;
int& val = now ->second=0;
if(ed <= last){
++it;
continue;
};
if(last<st)last = st;
auto jt = ++it;
assert(now != it);

assert(last < ed);
assert(last >=st);
int sweep_right = last;
for(;jt != seg.end() ; ++jt){
const int l = jt ->first.first;
const int r = - jt ->first.second;
if(sweep_right >=ed || l >= ed)break;
if(r <= sweep_right)continue;
if(l > sweep_right)val+= l - sweep_right;
sweep_right = r;
}
if(sweep_right < ed) val += ed - sweep_right;

// for next
last = max(ed,last);
}
// del max one
PIII p = *seg.begin();
for(auto it :seg){
if(it.second > p.second)p = it;
}
// cout << p.first.first << " " << p.first.second << " " << p.second<<"\n";
seg.erase(p.first);
return p.second;
}

int solve(){

int n,q;
cin >> n >> q;
map<PII,int>seg;
int ans =n+1;
for(int i=0; i<q ; ++i){
int l,r;
cin >> l>>r;
seg.insert({{--l,-r},0});
}
if(seg.size() < q)return 0;
while(!seg.empty() && ans!=0){

ans = min(ans,del(seg));
}
return ans;
}

int main(){

ios :: sync_with_stdio(0);
cin.tie(0);
std::cout.precision(8);
std::cout.setf( std::ios::fixed, std:: ios::floatfield );
TIII t;
int T;
cin >> T;
// cout << "T = " << T << "\n";
for(int t =1 ; t <= T; ++t){
auto ans = solve();
cout << "Case #"<<t<<": "<<ans<<"\n";
}
return 0;
}

github