思路讲解
思路很简单，一个块要么走上边，要么走下边（先忽略下去的那个块）
然后我们看走上面性价比高还是走下边性价比高，选择性价比高的。
再通过sort得到要从哪个块下去。
总的来说我觉得挺简单的，但是算法实现上有一些细节。
AC代码
https://codeforces.com/contest/2047/submission/295161620
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(5e3)+10;
ll n,T;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
cin>>n;
vector<pair<ll, ll> > A(n+10);
ll ans=0;
for(int i=1;i<=n;++i){
cin>>A[i].first;
}
for(int i=1;i<=n;++i){
cin>>A[i].second;
}
vector<ll> upBlock,dowBlock;
for(int i=1;i<=n;++i){
if(A[i].first>A[i].second){
ans+=A[i].first;
upBlock.push_back(A[i].second);
}else if(A[i].first<A[i].second){
ans+=A[i].second;
dowBlock.push_back(A[i].first);
}else{
ans+=A[i].second;
upBlock.push_back(A[i].second);
dowBlock.push_back(A[i].first);
}
}
ll lans=-1e18-7;
if(!upBlock.empty()){
sort(upBlock.begin(),upBlock.end(),greater<ll>());
lans=upBlock[0];
}
if(!dowBlock.empty()){
sort(dowBlock.begin(),dowBlock.end(),greater<ll>());
lans=max(dowBlock[0],lans);
}
ans+=lans;
cout<<ans<<endl;
}
}
|
心路历程（WA，TLE，MLE……）
https://codeforces.com/contest/2047/submission/295154910
1
2
3
4
5
6
7
| if(A[i].first>=A[i].second){
ans+=A[i].first;
upBlock.push_back(A[i].second);
}else{
ans+=A[i].second;
dowBlock.push_back(A[i].first);
}
|
应该是A[i].first==A[i].second的情况出了问题
好像和这个没关系，修了这个问题还是WA了。
https://codeforces.com/contest/2047/submission/295157816
最后发现是因为lans的初始化
没事这种lans（算max）的初始化还是直接-1e18+7走起，不管后面怎么样都不会出问题
1
2
3
4
5
6
7
8
9
10
11
| ll lans=-1e18-7;
if(!upBlock.empty()){
sort(upBlock.begin(),upBlock.end(),greater<ll>());
lans=upBlock[0];
}
if(!dowBlock.empty()){
sort(dowBlock.begin(),dowBlock.end(),greater<ll>());
lans=max(dowBlock[0],lans);
}
ans+=lans;
cout<<ans<<endl;
|