Hamburgers
贪心，注意到本来有的不会超过100，所以可以直接枚举。每次判断剩余的数量与需要数量的大小，如果小于那就赋值为0然后计算需要的价格，如果大于等于就减去用掉的数量。放到死循环里直至所有剩余的材料为0或者钱不够，然后再看剩余的钱可以做多少汉堡。还要注意如果某一种材料需要为0就把剩余数量赋值为0不然就出不来了。
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=5;
const int inf=0x3f3f3f3f;
ll n,r;
ll num[N],p[N],ne[N];
string a;
int main(){
//freopen("in.txt","r",stdin);
cin>>a;
for(int i=0;i<a.size();i++){
if(a[i]=='B') ne[0]++;
else if(a[i]=='S') ne[1]++;
else ne[2]++;
}
ll total=0;
for(int i=0;i<3;i++) cin>>num[i];
for(int i=0;i<3;i++) {
cin>>p[i];
total+=p[i]*ne[i];
if(ne[i]==0)num[i]=0;
}cin>>r;
for(int j=0;j<100;j++){
ll pr=0;
for(int i=0;i<3;i++){
if(num[i]<ne[i]){
pr+=p[i]*(ne[i]-num[i]);
num[i]=0;
}else{
num[i]-=ne[i];
}
}
if(r>=pr){
r-=pr;
n++;
}else{
break;
}
if(num[0]==0&&num[1]==0&&num[2]==0){
break;
}
}
n+=r/total;
cout<<n<<endl;
return 0;
}
Read Time
知道是二分但是不知道怎么判断，看了眼题解后才想通。我本来在想怎么样处理来回走的问题，因为我是在中间开始想的，原来只要从起始位置开始就处理好就不会有后面的问题。
相当于给每个指针一定的步数，它就可以控制一定的范围，目的是要所有的磁头的最大步数最小，因为只要比答案小就不可以，只要比答案大就一定可以，所以就是二分答案。
判断时循环磁头，如果到磁头的距离小于步数，那这个磁头就不可能够到；如果够得到且磁头不需要往回走。那么最终这个磁头到达的距离就是当前位置加上步数;如果需要往回走就要判断是先往右还是先往左取最大；然后去除在这个范围内的所有目标磁头，最后看可否包含所有目标磁头。
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int max_n=2e5;
const int inf=0x3f3f3f3f;
ll n,m;
ll h[max_n],p[max_n];
bool check(ll mid){
ll index=0,far;
for(int i=0;i<n;i++){
if(abs(h[i]-p[index])>mid) continue;
if(p[index]==h[i]) index++;
if(p[index]<h[i]){
far=max(h[i]+mid-2*(h[i]-p[index]),h[i]+(mid-(h[i]-p[index]))/2);
}else far=h[i]+mid;
while(p[index]<=far&&index<m){
index++;
}
}
return index==m;
}
int main(){
//freopen("in.txt","r",stdin);
cin>>n>>m;
for(int i=0;i<n;i++) cin>>h[i];
for(int i=0;i<m;i++) cin>>p[i];
ll l=0,r=abs(p[m-1]-h[0])+abs(p[0]-h[0])+min(abs(p[m-1]-h[0]),abs(p[0]-h[0]));
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
Matrix
本来直接打表准备找规律，最后发现老是wa，应该是因为当n变大了以后规律变了。
可以证明当i固定的时候，j越大，值越小；可以套两个二分，一开始二分答案，然后再判断里面二分j并记录大于的总个数，最后判断总个数和m的关系。(好菜啊，一下午才写了三个）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=2e5;
const ll inf=0x3f3f3f3f;
ll t,n,m;
ll fun(ll i,ll j){
return i*i+j*j+1e5*(i-j)+i*j;
}
bool check(ll t){
ll cnt=0;
for(int j=1;j<=n;j++){
ll l=0,r=n,ans=0;
while(l<=r){
ll mid=(l+r)>>1;
if(l==0&&r==0){
ans=0;
break;
}
if(fun(mid,j)<=t){
ans=mid;
l=mid+1;
}else r=mid-1;
}
cnt+=ans;
}
return cnt>=m;
}
int main(){
//freopen("in.txt","r",stdin);
cin>>t;
while(t--){
cin>>n>>m;
ll l=fun(1,n),r=fun(n,1),mid,ans;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else l=mid+1;
}
cout<<ans<<endl;
}
return 0;
}
序列变换
本来要求的是\(a[i]-a[j]>=i-j\),变成\(a[i]-i>=a[j]-j\),令新的数组\(b[i]=a[i]-i\)，求出其LIS，答案就是\(n-len\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=1e5+100;
const ll inf=0x3f3f3f3f;
int t,n,a[max_n],b[max_n];
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>t;
for(int j=1;j<=t;j++){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
b[i]=a[i]-i;
}
memset(a,0x3f,sizeof(a));
int len=1;
for(int i=0;i<n;i++){
if(b[i]>=a[len]) a[++len]=b[i];
else{
*upper_bound(a+1,a+len+1,b[i])=b[i];
}
}cout<<"Case #"<<j<<':'<<endl<<n-len<<endl;
}
return 0;
}