d731 - 11039 - Building designing
題目描述
題目要求找出在給定的樓層集合中，能夠建造出的最高大樓的高度。大樓的樓層面積必須嚴格遞增，且相鄰樓層的顏色必須不同（紅色和藍色）。樓層由正負整數表示，正數代表藍色，負數代表紅色，絕對值代表面積。
解題思路
首先，將給定的樓層按照顏色分成兩組：藍色樓層（正數）和紅色樓層（負數）。然後，分別對兩組樓層按照面積進行升序排序。接下來，使用貪心策略，交替選擇藍色和紅色樓層，以最大化大樓的高度。具體來說，從面積最大的樓層開始，依次嘗試選擇面積比當前樓層小的樓層，並確保顏色與上一層樓不同。由於已經分別對藍色和紅色樓層進行了排序，因此可以通過兩個指針來高效地實現這個過程。最後，比較兩種交替選擇方式（先藍色後紅色，或先紅色後藍色）所能建造的大樓高度，選擇最大值作為答案。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是樓層的數量。主要時間花費在排序上。
- 空間複雜度: O(n)，主要用於存儲樓層的面積。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
using namespace std;
int a[500001],b[500001],ait,bit;
inline int read(){
int a(0),f(1);
char c('0');
while(c>='0'||c=='-'){
if(c=='-'){
f=-1;
c=getchar_unlocked();
}
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a*f;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
int t,p,n;
t=read();
while(t--){
p=read();
ait=0;
bit=0;
while(p--){
n=read();
if(n>0){
a[ait]=n;
++ait;
}
else{
b[bit]=(-n);
++bit;
}
}
sort(a,a+ait);
sort(b,b+bit);
int ans1=0,ans2=0,i=ait-1,j=bit-1,now=1000000;
while(1){
while(i>=0&&now<a[i])--i;
if(i<0)break;
++ans1;
now=a[i];
while(j>=0&&now<b[j])--j;
if(j<0)break;
++ans1;
now=b[j];
}
now=1000000;i=ait-1;j=bit-1;
while(1){
while(j>=0&&now<b[j])--j;
if(j<0)break;
++ans2;
now=b[j];
while(i>=0&&now<a[i])--i;
if(i<0)break;
++ans2;
now=a[i];
}
write(max(ans1,ans2));
putchar_unlocked('\n');
}
}