30分贪心求助

P1489 猫狗大战

(没有TLE)
by AndyChen2005121 @ 2021-05-04 15:21:52


@[AndyChen2005121](/user/152652) ```cpp 13 6 6 6 6 6 6 6 7 7 7 7 7 7 ```
by 天南星魔芋 @ 2021-05-04 15:32:14


@[天南星魔芋](/user/399239) 改了 这次直接RE ```cpp #include <iostream> #include <vector> #include <cmath> using namespace std; int n; vector<int> a, b; int sum_a(){ int sum = 0; for(int i = 0; i < a.size(); i++) sum+=a[i]; return sum; } int sum_b(){ int sum = 0; for(int i = 0; i < b.size(); i++) sum+=b[i]; return sum; } int main() { cin >> n; int x; for(int i = 0; i < n/2; i++){ cin >> x; a.push_back(x); } for(int i = n/2;i<n;i++){ cin >> x; b.push_back(x); } int minn = abs(sum_a()-sum_b()); for(int i = 0; i < a.size(); i++){ for(int j = 0; j < b.size(); j++){ if(abs((sum_a()+a[i])-(sum_b()-b[j]))<=minn){ a.push_back(b[j]); b.erase(b.begin()+j-1); minn = abs(sum_a()-sum_b()); i = j = 0; } } } cout << sum_a() << " " << sum_b() << endl; return 0; } ```
by AndyChen2005121 @ 2021-05-04 15:53:07


@[AndyChen2005121](/user/152652) ``` #include<bits/stdc++.h> using namespace std; int n; vector<int>a,b; int sum_a(){ int sum=0; for(int i=0;i<a.size();i++)sum+=a[i]; return sum; } int sum_b(){ int sum=0; for(int i=0;i<b.size();i++)sum+=b[i]; return sum; } int main(){ cin>>n; int x; for(int i = 0; i < n/2; i++){ cin>>x; a.push_back(x); } for(int i = n/2;i<n;i++){ cin>>x; b.push_back(x); } int minn=abs(sum_a()-sum_b()); for(int i=0;i<a.size();i++){ for(int j=0;j<b.size();j++){ if(abs((sum_a()+a[i])-(sum_b()-b[j]))<=minn){ a.push_back(b[j]); b.erase(b.begin()+j);//!!!! minn=abs(sum_a()-sum_b()); i=j=0; } } } cout<<sum_a()<<" "<<sum_b()<<endl; return 0; } ```
by 天南星魔芋 @ 2021-05-04 16:08:44


@[天南星魔芋](/user/399239) 那为什么还是WA? 是不是第31行写挂了
by AndyChen2005121 @ 2021-05-04 16:59:41


@[AndyChen2005121](/user/152652) 不是,是因为贪心贪错了吧?
by 天南星魔芋 @ 2021-05-04 17:05:26


比如 ``` 4 1 2 3 4 ``` 和 ``` 4 1 2 4 3 ``` 程序答案不一样
by 天南星魔芋 @ 2021-05-04 17:07:23


@[天南星魔芋](/user/399239) 对于你这个hack数据,我把第31行改成 ```cpp if(abs((sum_a()+a[i])-(sum_b()-b[j]))<minn) ``` 答案就一样了, 但还是WA
by AndyChen2005121 @ 2021-05-04 17:39:01


@[AndyChen2005121](/user/152652) 再给一下码可以吗?QaQ
by 天南星魔芋 @ 2021-05-04 18:14:50


|