f374 - 分組 Grouping
題目描述
題目給定一個整數 n 代表組數，以及 n 個整數，每個整數代表一個組的總分。目標是找到一個組別，使得該組別的總分最大，並且輸出該組別的編號和總分。組別編號從 1 開始。
解題思路
這題可以使用貪心演算法解決。程式碼從標準輸入讀取組數 n，然後讀取每個組的總分。在讀取過程中，程式會迭代每個組別，並計算該組別的總分。如果該組別的總分大於或等於目前找到的最大總分，則更新最大總分和對應的組別編號。最後，程式輸出最大總分的組別編號和總分。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: 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 <stdio.h>
char it=0,n,clab,score,ans[9];
inline void write(int x) {
int stk[4],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
n=getchar_unlocked();
n-='0';
getchar_unlocked();
while(ans[it]=getchar_unlocked()){
if(ans[it]<'0')break;
++it;
}
score=0;
for(char i=it-1,c=1,tn=n,tmp=0;i>=0;++c,tn=n,tmp=0){
while(tn--){
if(i>=0)tmp+=ans[i]-'0';
--i;
}
if(tmp>=score){
clab=c;
score=tmp;
}
}
write(clab);
putchar_unlocked(' ');
write(score);
}