A - Profitable Interest Rate
void solve()
{
cin>>n>>m;
if(n>=m)cout<<n<<'\n';
else
{
int c=m-n;
if(c>=n)cout<<"0\n";
else cout<<n-c<<'\n';
}
return ;
}B - Buying Lemonade
其实就是判断排序后以每个点为最大值的时候所需要的柠檬水杯数是否大于给定的k
举个例子序列为1 2 3 4,k=5
假设1为最大值那么只能选1 1 1 1,此时选不满5个
假设2为最大值那么可以选1 2 2 2,此时可以选满5个,但是最坏情况下小于2号位置的所有位置会被多选择一次,所以输出k+(2-1)
假设L为最大值的时候可以选满k个则输出k+(L-1)
O(n)遍历即可(赛时写了个二分其实没必要)
int q[N];
bool check(int x)
{
int res=0;
_rep(i,1,x)
{
if(i!=x)res+=q[i];
else res+=(n-i+1)*q[i];
}
return res>=m;
}
void solve()
{
int yu=0,res=0;
cin>>n>>m;
_rep(i,1,n)cin>>q[i];
sort(q+1,q+1+n);
int l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
check(mid)?r=mid:l=mid+1;
}
cout<<l-1+m<<'\n';
return ;
}C - Concatenation of Arrays
题意
给定n个长度为2的数组,现在要把这n个数组放到一排,问怎么放可以使这个长度为2*n的新数组逆序对最小
思路
假设单纯要使一个数组逆序对最小,直接sort即可
现在要使n个长度为2的小数组 拼在一起后的数组逆序对最少,猜测只需要改变一下sort的排序规则即可
一开始暴力判断 长度为2的小数组的前后顺序,判断两两之间的关系,假设a在前使得两两逆序对更少,那就把a排在前面,然后WA2了
发现这个排序具有传递性,也就是这个排序的‘=’可能是因为a==b,b==c那么默认a==c
所以要特判一下=的情况,例如下面这个样例
输入
1
4
7 8 1 10 3 4 5 6 {1 10}=={3 4},{1 10}=={5 6},{1 10}=={7 8},但是{3 4}<{5 6}<{7 8},所以相等状态下还要加一个大小关系的特判
错误输出:3 4 7 8 1 10 5 6 加了if(x==y)return a.first+a.second<b.first+b.second;之后 输出(正确):3 4 1 10 5 6 7 8D - Skipping
题意
简单来说,遇到这个题目
跳过的话下一次只能选择下标<=i的第一个没遇到过的题目并且或者a[i]分
提交的话下一次只能选择下标<=b[i]的第一个没遇到过的题目并且不得分
思路
模拟了一下样例很快就能发现,在i号点我有两个策略:
1:开始一直提交问题,把所有<=i的并且没遇到过的题目分数都加上
2:直接或者间接跳到下一个下标大于i的点,这样才能赚更多的分数
推到这一步之后,就可以想到,最后答案一定是遍历每个点,然后每个点都计算一下我跳过最少的分数到达这个点之后然后选择1策略能得到的分数,然后每次更新答案
所以这道题就是一个最短路问题,dist[i]维护的是从1号点到i号点所需要跳过(跳过之后就不能再选,就亏了)所亏的最少分数,建立所有i到b[i]的权值为a[i]的边以及所有i+1到i的权值为0的边,最后答案取
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
const int N=1e6+10,INF=4e18;
int n,m;
int e[N],ne[N],w[N],idx,h[N];
int a[N],b[N];
int dist[N];
void add(int a,int b,int c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
bool st[N];
void dij()
{
memset(dist,0x3f,(n+1)*8);
memset(st,false,(n+1));
priority_queue<PII,vector<PII>,greater<PII>>que;
que.push({0,1});
dist[1]=0;
while(que.size())
{
auto t=que.top();
que.pop();
int u=t.se;
if(st[u])continue;
st[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i],k=w[i];
if(dist[j]>dist[u]+k)
{
dist[j]=dist[u]+k;
que.push({dist[j],j});
}
}
}
return ;
}
int qian[N];
void solve()
{
cin>>n;
_rep(i,1,n)cin>>a[i],qian[i]=qian[i-1]+a[i];
memset(h,-1,(n+1)*2*8);
_rep(i,1,n)
{
cin>>b[i];
add(i,b[i],a[i]);//i跳到b[i]要亏a[i]
if(i!=n)add(i+1,i,0);
}
dij();
int res=0;
_rep(i,1,n)
{
// cout<<dist[i]<<" ";
res=max(res,qian[i]-dist[i]);
}
// cout<<"\n";
cout<<res<<'\n';
return ;
}
signed main()
{
IOS;
int T=1;
cin>>T;
while(T--)
solve();
return 0;
}