Week1 基础算法

算法"/>

Week1 基础算法

文章目录

• A - Raising Modulo Numbers
• B - 起床困难综合症
• C - 激光炸弹
• D - Tallest Cow
• E - Best Cow Fences
• F - 借教室
• G - Cinema
• H - Balanced Lineup
• I - Best Cow Line
• J - Fence Repair
• K - Radar Installation
• L - Corral the Cows
• M - 超级钢琴
• N - 糖果传递
• O - Too Rich

本周专题：常见基础算法
知识点：
A-B：位运算
C-D：前缀和、差分
E-F：简单二分
G：离散化
H：ST表（倍增）
I-K：贪心
L-O：综合练习

A - Raising Modulo Numbers

INPUT

3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

OUTPUT

2
13195
13

打个快速幂。

#include<iostream>
#define llg long long
using namespace std;
int n,mod;llg ksm(int base,int power,int m)
{llg ans=1;base%=m;while(power){if(power&1)ans=ans*base%m;power>>=1;base=base*base%m;}return ans;
}int main()
{cin>>n;while(n--){int t;cin>>mod;cin>>t;llg ans=0;while(t--){int a,b;scanf("%d%d",&a,&b);llg temp=ksm(a,b,mod);//printf("ksm(%d,%d,%d):%lld\n",a,b,mod,temp);ans+=temp;ans%=mod;}printf("%lld\n",ans);}return 0;
}

---

B - 起床困难综合症

链接

位运算特点：二进制下不进位
尽量让可控范围的每一位经过操作之后都是1.

#include<bits/stdc++.h>
using namespace std;int n,m;
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
pair<string,int> a[100005];int cal(int bit,int now)
{for(int i=1;i<=n;i++){int x=a[i].second>>bit&1;//把操作数的当前位提取出来if(a[i].first=="AND") now&=x;if(a[i].first=="OR") now|=x;if(a[i].first=="XOR") now^=x;}return now;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){string s;int x;cin>>s>>x;a[i]=make_pair(s,x);}int val=0,ans=0;for(int bit=29;bit>=0;bit--)//枚举每个二进制位（从高位开始）{int res0=cal(bit,0);//这一位是0，经过如题操作后得到的结果int res1=cal(bit,1);//这一位是1，经过如题操作后得到的结果if(val+(1<<bit)<=m&&res0<res1)//不能超过最大值val+=1<<bit,ans+=res1<<bit;else ans+=res0<<bit;}cout<<ans<<endl;return 0;
}

---

C - 激光炸弹

链接

二维前缀和。

#include<iostream>
using namespace std;
int n,m,mp[5010][5010],maxn;
const int N=5001;int main()
{cin>>n>>m;for(int i=1;i<=n;i++){int x,y,v;cin>>x>>y>>v;mp[x+1][y+1]+=v;//横纵坐标都加1，防止之后越界}for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)mp[i][j]=mp[i][j-1]+mp[i-1][j]-mp[i-1][j-1]+mp[i][j];//二维前缀和for(int i=m;i<=N;i++)for(int j=m;j<=N;j++){int temp=mp[i][j]-mp[i-m][j]-mp[i][j-m]+mp[i-m][j-m];//算出每一个边长为m的正方形内包含的数maxn=max(maxn,temp);}cout<<maxn<<endl;return 0;
}

---

D - Tallest Cow

链接

差分，让左右端点中间陷下去（高度最少-1）.注意避免关键字冲突。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;#define ll long long
pair<ll,ll> a[10100];
map<ll,ll> q;
ll n,m,i,j,k,p,h,c[10100],d[10100];int main()
{cin>>n>>p>>h>>m;for (i=1;i<=m;i++){ll A,B;cin>>A>>B;if(A>B) swap(A,B);if(q[A]!=B)//关键字不冲突{a[i]=make_pair(A,B);q[A]=B;d[A+1]--;d[B]++;}}for (i=1;i<=n;i++)c[i]=c[i-1]+d[i];for (i=1;i<=n;i++)cout<<c[i]+h<<endl;
}

---

E - Best Cow Fences

链接
给定正整数数列A，求一个平均数最大的、长度不小于L的（连续的）子段。

二分答案求平均值。

#include<iostream>
using namespace std;
double a[100001],b[100001],pre[100001];
int n,len;int main()
{cin>>n>>len;for(int i=1;i<=n;i++)scanf("%lf",&a[i]);double eps=1e-5;double l=-1e5,r=1e5;while(l+eps<r){double mid=(l+r)/2;for(int i=1;i<=n;i++) b[i]=a[i]-mid;for(int i=1;i<=n;i++)pre[i]=pre[i-1]+b[i];double minn=1e5,ans=-1e5;for(int i=len;i<=n;i++){minn=min(minn,pre[i-len]);ans=max(ans,pre[i]-minn);}if(ans>=0) l=mid;else r=mid;}cout<<int(r*1000)<<endl;return 0;
}

---

F - 借教室

链接

前缀和+差分+二分答案

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N],dif[N],temp[N];
int d[N],s[N],t[N];
int n,m;
bool check(int x)
{memset(dif,0,sizeof(dif));for(int i=1;i<=x;i++){dif[s[i]]-=d[i];dif[t[i]+1]+=d[i];}for(int i=1;i<=n;i++){temp[i]=temp[i-1]+dif[i];if(temp[i]+a[i]<0) return 0;}return 1;
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int j=1;j<=m;j++)scanf("%d%d%d",&d[j],&s[j],&t[j]);if(check(m)){cout<<'0';return 0;}int l=1,r=m,mid,ans;while(l<r){mid=(l+r)/2;if(check(mid)) l=mid+1;else r=mid;}cout<<"-1\n"<<l;
}

---

G - Cinema

链接

先把所有的数据读入，离散化一下，用桶装每种语言对应的教授的个数。根据题意找到最合适的电影序号。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N],b[N],c[N],d[N*3],box1[N*3],n,m,cnt,maxn1,num;
int mem,maxn2;inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}int main()
{n=read();for(int i=1;i<=n;i++) a[i]=read(),d[++cnt]=a[i];m=read();for(int i=1;i<=m;i++)b[i]=read(),d[++cnt]=b[i];for(int i=1;i<=m;i++)c[i]=read(),d[++cnt]=c[i];sort(d+1,d+cnt+1);int total=unique(d+1,d+cnt+1)-d;for(int i=1;i<=n;i++){a[i]=lower_bound(d+1,d+total+1,a[i])-d;box1[a[i]]++;}for(int i=1;i<=m;i++){b[i]=lower_bound(d+1,d+total+1,b[i])-d;c[i]=lower_bound(d+1,d+total+1,c[i])-d;int ansx=box1[b[i]],ansy=box1[c[i]];if(ansx>maxn1||(ansx==maxn1&&ansy>maxn2))num=i,maxn1=ansx,maxn2=ansy;}//cout<<"maxn:"<<maxn<<" num:"<<num<<endl;if(num==0) cout<<1<<endl;else cout<<num<<endl;return 0;
}

---

H - Balanced Lineup

典型RMQ。

#include<bits/stdc++.h>
using namespace std;
int n,m,f[180010][20],g[180010][20];inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}int main()
{cin>>n>>m;memset(g,0x3f,sizeof(g));for(int i=1;i<=n;i++)f[i][0]=g[i][0]=read();int t=log(n)/log(2);for(int j=1;j<=t;j++)for(int i=1;i<=n-(1<<j)+1;i++)f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]),g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);while(m--){int r,l;l=read(),r=read();int k=log(r-l+1)/log(2);int high=max(f[l][k],f[r-(1<<k)+1][k]);int low=min(g[l][k],g[r-(1<<k)+1][k]);printf("%d\n",high-low);}return 0;		
}

---

I - Best Cow Line

链接

两端不同取小，两端相同向内比较，直到不同位置（中间的一直相同的话直接从左端点到右端点了）。

#include<iostream>
using namespace std;
char a[2005];
int n;int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int l=1,r=n,p=0;while(l<=r){if(a[l]<a[r]) cout<<a[l++];else if(a[r]<a[l]) cout<<a[r--];else{int ll=l,rr=r;while(a[ll]==a[rr]&&ll<=rr)ll++,rr--;if(a[ll]<=a[rr])cout<<a[l++];else cout<<a[r--];}p++;if(p%80==0) cout<<endl;}return 0;
}

---

J - Fence Repair

链接

（二叉哈夫曼树？）
每次选两个最小的合并。

#include<stdio.h>
#include<queue>
#include<iostream>
using namespace std;
int main()
{int n,m,a,b;long long sum;while(~scanf("%d",&n)){priority_queue<int,vector<int>, greater<int> >Q;for(int i=1;i<=n;i++){scanf("%d",&m);Q.push(m);}sum=0;while(Q.size()>1) {a=Q.top();Q.pop();b=Q.top();Q.pop(); Q.push(a+b);sum+=a+b;}printf("%lld\n",sum);}return 0; 
}

---

K - Radar Installation

链接

以每个岛为圆心画圆，求出在x轴上的左右端点。坐标在左右端点之间的雷达可以覆盖到该岛。把这些点对按照右端点大小排序。下一点对的左端点若在当前点对的右边，就需要加装一个雷达，否则当前雷达也能覆盖到下一座岛屿。（画图就好理解啦，又怪我太懒了）

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct island
{double l,r;
};
int n;
double d;
int cnt=0;
bool cmp(island x,island y)
{return x.r<y.r;
}
int main()
{while(cin>>n>>d){if(n==0&&d==0) break;++cnt;island is[1010];int ok=1,sum=1;for(int i=1;i<=n;i++){double x,y;cin>>x>>y;if(y>d) ok=0;double dis=sqrt(d*d-y*y);is[i].l=x-dis,is[i].r=x+dis;}if(!ok){printf("Case %d: -1\n",cnt);continue;}sort(is+1,is+n+1,cmp);double now=is[1].r;for(int i=2;i<=n;i++){if(is[i].l>now){now=is[i].r;sum++;}}printf("Case %d: %d\n",cnt,sum);}
}

---

L - Corral the Cows

链接

坐标的范围在1 ~ 10000，如果直接开二维数组遍历显然不现实，再看N的范围最大是500，那么我们就可以将坐标离散化后存在一个数组里，用这个数组来进行前缀和运算的操作，就会大大降低时间复杂度。

#include<iostream>
#include<algorithm>
using namespace std;
int num[1001],x[1001],y[1001];
int sum[1001][1001],c,n,cnt,total;bool check(int len)
{for(int x1=1,x2=1;x2<=total;x2++){ while(num[x2]-num[x1]+1>len) x1++;//离散化前的左右边界横坐标距离已经超过len，左边界右移 for(int y1=1,y2=1;y2<=total;y2++){while(num[y2]-num[y1]+1>len) y1++;//离散化前的上下边界纵坐标距离已经超过len，下边界上移 if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]>=c)//在这个区域内的三叶草数量超过题目要求的 return true;}}return false;
}
int main()
{cin>>c>>n;for(int i=1;i<=n;i++){scanf("%d%d",&x[i],&y[i]);num[++cnt]=x[i],num[++cnt]=y[i];//所有可能出现的坐标 }sort(num+1,num+cnt+1);total=unique(num+1,num+cnt+1)-num-1;for(int i=1;i<=n;i++){x[i]=lower_bound(num+1,num+total+1,x[i])-num;y[i]=lower_bound(num+1,num+total+1,y[i])-num;//离散化一下 sum[x[i]][y[i]]++;//离散化过后对应坐标处有一株三叶草 }for(int i=1;i<=total;i++)for(int j=1;j<=total;j++)sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+sum[i][j];//二维前缀和 int l=1,r=10000;while(l<r) {int mid=(l+r)>>1;if(check(mid)) r=mid;else l=mid+1;}cout<<r<<endl;return 0;
}

---

M - 超级钢琴

链接

我说这是本周最难的题目一点也不为过吧QAQ。

可以先做一下这一题：P1631 序列合并
看起来没关系但可以用到这种思想（实际上我想说我做了这题之后才能看懂题解，躺）

先把第一列的数都放到优先队列里，n次循环，每次弹出优先队列里最小的数，从这个最小的数所在行中取下一个。

#include<bits/stdc++.h>
#define llg long long
using namespace std;const int N=1e5+10;
llg a[N],b[N],c[N],point[N];
int n;
struct Node
{int val,pos;bool operator < (const Node& x) const{return val>x.val;}
};priority_queue<Node>q;
int main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++){scanf("%lld",&b[i]);point[i]=1;Node temp;temp.pos=i,temp.val=a[1]+b[i];q.push(temp);}for(int i=1;i<=n;i++){int now=q.top().pos;int v=q.top().val;//cout<<"now:"<<now<<" v:"<<v<<endl;printf("%d ",v);q.pop();Node temp;temp.pos=now,++point[now],temp.val=a[point[now]]+b[now];q.push(temp);}return 0;
}

来看这道题：

首先，题目是要求区间和，可以考虑用前缀和。
控制了区间长度在[L,R]区间内，对于每个合法的左端点i，右端点可能的位置为 m i n ( n , i + R − 1 ) min(n,i+R-1) min(n,i+R−1)
我们可以对每个左端点x求一个 t ( x + L − 1 < = t < = m i n ( n , x + R − 1 ) ) t(x+L-1<=t<=min(n,x+R-1)) t(x+L−1<=t<=min(n,x+R−1))。把 s u m [ x , t ] sum[x,t] sum[x,t]，即 p r e [ t ] − p r e [ x − 1 ] pre[t]-pre[x-1] pre[t]−pre[x−1]放入优先队列，

for(int i=1;i+L-1<=n;i++)
q.push((Node){i,i+L-1,min(n,i+R-1),query(i+L-1,min(n,i+R-1))});

k次循环，每次从优先队列队首取出一个元素（优先队列内放四元组 ( x , l , r , t ) (x,l,r,t) (x,l,r,t),x是左端点,l和r是右端点的范围,t是当前解的右端点的位置）

struct Node
{int x,l,r,t;bool operator < (const Node& y) const{return pre[t]-pre[x-1]<pre[y.t]-pre[y.x-1];}
};
priority_queue<Node> q;

对该左端点来说，最优的右端点对应的答案已经被计入，该右端点已被弹出，但仍有若干次优右端点分布在最优右端点的左右，将它们放入优先队列（注意控制边界）。弹出k个元素即找到了k个区间，求解完成。

int x=q.top().x,l=q.top().l,r=q.top().r,t=q.top().t;
q.pop();
ans+=pre[t]-pre[x-1];
if(t!=l) q.push((Node){x,l,t-1,query(l,t-1)});
if(t!=r) q.push((Node){x,t+1,r,query(t+1,r)});

现在的问题在于对于每个左端点x，怎么找到t的位置。 p r e [ t ] − p r e [ x − 1 ] pre[t]-pre[x-1] pre[t]−pre[x−1]， p r e [ x − 1 ] pre[x-1] pre[x−1]是确定的，只需要让 p r e [ t ] pre[t] pre[t]最大即可，在 ( x + L − 1 < = t < = m i n ( n , x + R − 1 ) ) (x+L-1<=t<=min(n,x+R-1)) (x+L−1<=t<=min(n,x+R−1))范围内求 p r e [ t ] pre[t] pre[t]的最大值（只不过我们用ST表记录下的是下标），RMQ问题。这就好解了。

void init()
{for(int i=1;i<=n;i++) st[i][0]=i;int t=log(n)/log(2);for(int j=1;j<=t;j++)for(int i=1;i+(1<<j)-1<=n;i++){int x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];st[i][j]=pre[x]>pre[y]?x:y;}
}int query(int l,int r)
{int k=log(r-l+1)/log(2);int x=st[l][k],y=st[r-(1<<k)+1][k];return pre[x]>pre[y]?x:y;
}

完整代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=500010;
int st[N][30];
long long pre[N],ans;
int n,k,L,R;void init()
{for(int i=1;i<=n;i++) st[i][0]=i;int t=log(n)/log(2);for(int j=1;j<=t;j++)for(int i=1;i+(1<<j)-1<=n;i++){int x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];st[i][j]=pre[x]>pre[y]?x:y;}
}int query(int l,int r)
{int k=log(r-l+1)/log(2);int x=st[l][k],y=st[r-(1<<k)+1][k];return pre[x]>pre[y]?x:y;
}
struct Node
{int x,l,r,t;bool operator < (const Node& y) const{return pre[t]-pre[x-1]<pre[y.t]-pre[y.x-1];}
};priority_queue<Node> q;int main()
{scanf("%d%d%d%d",&n,&k,&L,&R);for(int i=1;i<=n;i++){scanf("%lld",&pre[i]);pre[i]+=pre[i-1];}init();for(int i=1;i+L-1<=n;i++)q.push((Node){i,i+L-1,min(n,i+R-1),query(i+L-1,min(n,i+R-1))});while(k--){int x=q.top().x,l=q.top().l,r=q.top().r,t=q.top().t;q.pop();ans+=pre[t]-pre[x-1];if(t!=l) q.push((Node){x,l,t-1,query(l,t-1)});if(t!=r) q.push((Node){x,t+1,r,query(t+1,r)});}cout<<ans;return 0;
}

---

N - 糖果传递

链接

可以先做：
P1031 [NOIP2002 提高组] 均分纸牌
104. 货仓选址

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int N=1000010;
long long a[N],pre[N],n,ave;
long long sum,ans;int main()
{cin>>n;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum+=a[i];}ave=sum/n;//最终每个人分到的糖果for(int i=1;i<=n;i++){a[i]-=ave;pre[i]=pre[i-1]+a[i];//相当于将前i个人视作一个整体，这个整体需要给后面的人（或者从后面的人处取得）一定的糖果数}//下面利用的主要是中位数的性质（到各数距离和最小）sort(pre+1,pre+n+1);int mid=pre[(n+1)/2];for(int i=1;i<=n;i++)ans+=abs(mid-pre[i]);cout<<ans;
}

---

O - Too Rich

INPUT

3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0

OUTPUT

9
-1
36

先考虑朴素的贪心：
要尽可能多拿出来钱币 <-> 把所有钱币都拿出来之后尽量少拿回去几个（当然还是得凑出来正确面额的）。想尽量少拿，就得尽量拿大面值的。于是就有了我的第一版朴素贪心：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
long long a[N],pre[N],n,ave;
long long sum,ans;int main()
{cin>>n;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum+=a[i];}ave=sum/n;for(int i=1;i<=n;i++){a[i]-=ave;pre[i]=pre[i-1]+a[i];}sort(pre+1,pre+n+1);int mid=pre[(n+1)/2];for(int i=1;i<=n;i++)ans+=abs(mid-pre[i]);cout<<ans;
}

毫无疑问WA了。对于下面这组数据：

2
250 1 0 0 3 1 0 1 0 0 0
190 0 0 0 5 100 0 0 0 0 0

肉眼观察可得输出应该是 2 5 ，但上面的程序输出 -1 -1（凑不出250和190），显然是不对的。以第一组数据为例，上面的程序相当于先取了50，这导致剩下来的一个1，三个20，一个200凑不出250。主要原因就是20不是50的约数，200不是500的约数。
50可能取奇数次，这是20所凑不出的。
500可能取奇数次，这是200所凑不出的。
于是我们枚举以下四种情况

（50和500都是偶数个，不先取50和500）
（50为奇数个，500为偶数个，即我们先取一个50）
（50为偶数个，500为奇数个，即我们先取一个500）
（50为奇数个，500为奇数个，即我们先取一个50和一个500）

之后对于50和500都成对地取。
每次取50或500的时候就取偶数个。然而消除的时候也消除偶数个。
这样的枚举，就消除了这个两个特殊关系的影响啦。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<time.h>
#include<bitset>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
const int N=55,M=0,Z=1e9+7,maxint=2147483647,ms31=522133279,ms63=1061109567,ms127=2139062143;const double eps=1e-8,PI=acos(-1.0);//.0
int casenum,casei;
UI m;
int a[12],c[12],b[12],e[12];
int ans;
void init()
{c[1]=1;c[2]=5;c[3]=10;c[4]=20;c[5]=50;c[6]=100;c[7]=200;c[8]=500;c[9]=1000;c[10]=2000;
}
int cntmin(UI tmp,int p)
{int num=0;for(int i=p;i>=1;i--){if(e[i]==-1){int g=min((UI)b[i],tmp/c[i]);num+=g;tmp-=g*c[i];}else{int g=min((UI)b[i],tmp/c[i]);if(g&1)--g;num+=g;tmp-=g*c[i];}}if(tmp==0)return num;else return -1;
}
void tryit()
{if(e[5]>a[5]||e[8]>a[8])return;MS(b,0);int num=e[5]+e[8];UI tmp=e[5]*50+e[8]*500;for(int i=1;i<=10;i++){if(e[i]==-1){num+=a[i];b[i]=a[i];tmp+=a[i]*c[i];}else{b[i]=a[i]-e[i];if(b[i]&1)--b[i];num+=b[i];tmp+=b[i]*c[i];}if(tmp>=m){int more=tmp-m;int over=cntmin(more,i);if(~over){num-=over;gmax(ans,num);}return;}}
}
int main()
{init();scanf("%d",&casenum);for(casei=1;casei<=casenum;casei++){scanf("%d",&m);for(int i=1;i<=10;i++)scanf("%d",&a[i]);MS(e,-1);ans=-1;e[5]=0;e[8]=0;tryit();e[5]=0;e[8]=1;tryit();e[5]=1;e[8]=0;tryit();e[5]=1;e[8]=1;tryit();printf("%d\n",ans);}return 0;
}

我自己写调了好久还是挂了，这是粘贴这篇博客的代码以及部分文字。特别鸣谢233

但是如果有更多(20<->50)(200<->500)这样的数对，这样整活就太麻烦了，可以考虑DFS在每个面值处递归两次（一次全部取，一次少取一个），这样写起来比打补丁的贪心简洁多了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>using namespace std;
typedef long long ll;
const int v[10]= {1,5,10,20,50,100,200,500,1000,2000};
int p,c[10],totval,totcnt,ans;void dfs(int left,int cur,int cnt)
{if(left<0) return;if(left==0) ans=min(ans,cnt);else if(cur>=0){int num=min(left/v[cur],c[cur]);dfs(left-num*v[cur],cur-1,cnt+num);//全部取出if(num>0) dfs(left-(num-1)*v[cur],cur-1,cnt+(num-1));//少取一个}
}int main()
{int T;cin>>T;while(T--){totcnt=0,totval=0;scanf("%d",&p);for(int i=0;i<10;i++){scanf("%d",&c[i]);totcnt+=c[i];totval+=c[i]*v[i];}ans=0x3f3f3f3f;dfs(totval-p,9,0);if(ans==0x3f3f3f3f) printf("-1\n");else printf("%d\n",totcnt-ans);}return 0;
}