e559 - 10664 - Luggage
題目描述
題目要求判斷給定一組行李重量，是否能將這些行李分成兩組，使得兩組行李的總重量相等。
解題思路
這題的核心是判斷給定的行李重量集合是否能分割成兩個總和相等的子集。這是一個典型的子集和問題 (Subset Sum Problem)。程式碼使用動態規劃 (Dynamic Programming) 來解決這個問題。首先計算所有行李的總重量 ans。如果 ans 是奇數，則不可能分割成兩個重量相等的子集，直接輸出 "NO"。如果 ans 是偶數，則計算目標重量 a2 = ans / 2。然後，建立一個布林陣列 k，大小為 a2 + 1，用於記錄是否能找到總和為 j 的子集，其中 0 <= j <= a2。初始化 k[0] 為 true，表示可以找到總和為 0 的空子集。接著，遍歷每個行李的重量 arr[i]，並從 a2 到 arr[i] 倒序遍歷 k 陣列。如果 k[j] 為 true，則表示可以找到總和為 j 的子集，那麼就可以找到總和為 j + arr[i] 的子集，將 k[j + arr[i]] 設為 true。最後，判斷 k[a2] 是否為 true。如果為 true，則表示可以找到總和為 a2 的子集，因此可以將行李分割成兩個重量相等的子集，輸出 "YES"。否則，輸出 "NO"。
複雜度分析
- 時間複雜度: O(n * sum)，其中 n 是行李的數量，sum 是行李總重量。
- 空間複雜度: O(sum)，其中 sum 是行李總重量。
程式碼
#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>
int arr[101],it;
int main(){
char a;
while(a=getchar_unlocked())
if(a=='\n')break;
int ans=0,tmp=0,bk=0;
while(a=getchar_unlocked()){
if(a=='\n'||a==-1){
ans+=tmp;
arr[it]=tmp;
++it;
tmp=0;
if(ans%2){
putchar_unlocked('N');
putchar_unlocked('O');
putchar_unlocked('\n');
}
else{
int a2=ans/2,k[a2+1]={0};
for(int i=0;i<it;++i)
for(int j=a2-arr[i];j>=0;--j)
if(k[j]||j==0)
k[j+arr[i]]=1;
if(k[a2]){
putchar_unlocked('Y');
putchar_unlocked('E');
putchar_unlocked('S');
putchar_unlocked('\n');
}
else{
putchar_unlocked('N');
putchar_unlocked('O');
putchar_unlocked('\n');
}
}
it=0;
ans=0;
if(a==-1)bk=1;
}
else if(a==' '){
ans+=tmp;
arr[it]=tmp;
++it;
tmp=0;
}
else{
tmp*=10;
tmp+=a-'0';
}
if(bk)break;
}
}