A - Profitable Interest Rate
1
2
3
4
5
6
7
8
9
10
11
12
13
| void solve(){
int a,b;cin>>a>>b;
if(a>=b){
cout<<a<<"\n";
}else{
int k=2*a-b;
if(k>0){
cout<<k<<"\n";
}else{
cout<<0<<"\n";
}
}
}
|
B - Buying Lemonade
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void solve(){
int n,k;cin>>n>>k;
vector<int>a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());
int sum=0,ans=0,mn=0;
for(int i=0;i<n;i++){
a[i]-=mn;
if(sum+a[i]*(n-i)<k){
sum+=a[i]*(n-i);
mn+=a[i];ans+=a[i]*(n-i);
}else{
ans+=k-sum;
break;
}
ans++;
}
cout<<ans<<"\n";
}
|
C - Concatenation of Arrays
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void solve(){
int n;cin>>n;
vector<array<int,3>>a(n);
for(int i=0;i<n;i++){
cin>>a[i][0]>>a[i][1];
a[i][2]=a[i][0]+a[i][1];
}
sort(a.begin(),a.end(),[&](auto l,auto r){
if(l[2]!=r[2])return l[2]<r[2];
else return min(l[0],l[1])<min(r[0],r[1]);
});
for(int i=0;i<n;i++){
cout<<a[i][0]<<" "<<a[i][1]<<" ";
}
cout<<"\n";
}
|
D - Skipping
只有答题才能得分，所以跳题相当于花费a[i]从位置i转移到b[i]
答题就是花费0从i转移到i-1
最终答案就是所有能遍历到的位置上的a[i]-cost[i]
b[i]小于等于i时选择跳过是不明智的，因为此时在到达b[i]的过程中通过答题到b[i]能获得的分数一定更大
i 到 j 有两种方法，第一种是 j=b[i]，直接从 i 跳到 j ；第二种是 i<j<b[i] ，从 i 跳到 b[i] 再向左答题到 j，两种方法的花费都是a[i]，
所以我们遍历所有位置，每次取能到当前位置且花费最小，转移到当前位置求每个能遍历到的位置的最小花费
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
| void solve(){
int n;cin>>n;
vector<pair<int,int>>a(n+1);
for(int i=1;i<=n;i++) cin>>a[i].first;
for(int i=1;i<=n;i++) cin>>a[i].second;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push({a[1].first,a[1].second});
vector<int>dp(n+1,1e18);
dp[1]=0;
for(int i=2;i<=n;i++){
while(pq.size()&&pq.top().second<i){
pq.pop();
}
if(pq.empty()){
break;
}
dp[i]=pq.top().first;
if(a[i].second>i){
pq.push({dp[i]+a[i].first,a[i].second});
}
}
int sum=0,ans=0;
for(int i=1;i<=n;i++){
sum+=a[i].first;
ans=max(ans,sum-dp[i]);
}
cout<<ans<<"\n";
}
|