算法进阶指南：第一章练习题

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

1.The Pilots Brothers' refrigerator

牛客竞赛-The Pilots Brothers' refrigerator

116. 飞行员兄弟 - AcWing题库

开关问题的特点是每个开关只会作用某个特定范围所以每个开关最多操作一次且操作先后次序对最后结果无影响。用16位二进制存储状态1表示关0表示开。枚举所有的操作情况1表示拨动开关0表示不操作。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=10007;
const int N=1010;
int mp[4][4];
void solve()
{
	vector<pii>ans;
	string s;
	int c=0;
	rep(i,0,4){
		cin>>s;
		rep(j,0,4) if(s[j]=='+') c+=(1<<4*i+j);
	}
	rep(i,0,4) rep(j,0,4){
		rep(k,0,4) mp[i][j]+=(1<<4*i+k)+(1<<4*k+j);
		mp[i][j]-=(1<<4*i+j); 
	}
	rep(i,0,1<<16){
		int cc=c;
		vector<pii>v;
		rep(j,0,16) if(i>>j&1){
			int x=j/4,y=j%4;
			cc^=mp[x][y];
			v.push_back({x+1,y+1});
		}
		if(cc==0&&(ans.size()==0||v.size()<ans.size())) ans=v;
	}
	cout<<ans.size()<<endl;
	for(auto i:ans) cout<<i.fi<<" "<<i.se<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_; 
	while(_--){
		solve();
	}
	return 0;
}

2.占卜DIY

牛客竞赛-占卜DIY

117. 占卜DIY - AcWing题库

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=10007;
const int N=1010;
struct node{
	deque<pii>q;
}T[N];
int mp(char ch)
{
	if(ch>='2'&&ch<='9') return ch-'0';
	if(ch=='0') return 10;
	if(ch=='A') return 1;
	if(ch=='J') return 11;
	if(ch=='Q') return 12;
	if(ch=='K') return 13;
}
void solve()
{
	char ch;
	rep(i,1,14){
		rep(j,0,4) cin>>ch,T[i].q.push_back({mp(ch),0});
	}
	rep(i,0,4){
		int x=T[13].q[i].fi;
		while(x!=13){
			T[x].q.push_front({x,1});
			int t=x;
			x=T[x].q[T[x].q.size()-1].fi;
			T[t].q.pop_back();
		}
	}
	map<int,int>mmp;
	rep(i,1,13){
		for(auto j:T[i].q) if(j.se&&j.fi!=13) ++mmp[j.fi];
	}
	int cnt=0;
	for(auto i:mmp) if(i.se==4) ++cnt;
	cout<<cnt;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_; 
	while(_--){
		solve();
	}
	return 0;
}

3.Fractal

牛客竞赛-Factal

118. 分形 - AcWing题库

用cal(n,x,y)表示将规模为n的且左上角坐标为(x,y)的图像填写在char a[][]中。递归填写完了之后直接输出a即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
#define INF 1e12
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1010;
char a[N][N];
void cal(int n,int x,int y)
{
	if(n==1){
		a[x][y]='X';
		return;
	}
	int len=pow(3,n-2);
	cal(n-1,x,y),cal(n-1,x,y+2*len),cal(n-1,x+len,y+len),cal(n-1,x+2*len,y),cal(n-1,x+2*len,y+2*len);
}
void solve()
{
	rep(i,0,N) rep(j,0,N) a[i][j]=' ';
	int n;
	while(cin>>n){
		if(n==-1) break;
		cal(n,0,0);
		int len=pow(3,n-1);
		rep(i,0,len){
			rep(j,0,len) cout<<a[i][j];
			cout<<endl;
		}
		cout<<"-"<<endl;
	}
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_; 
	while(_--){
		solve();
	}
	return 0;
}

 4.Raid

牛客竞赛-Raid

119. 袭击 - AcWing题库

对于某一个特工如果只有一个维度只用找到离x最近的一个核电站。如果是二维最短的答案距离这个核电站不会太远检查相邻的几个更新答案即可。

先把特工核电站按照x从小到大排序。双指针算法遍历特工i每次在核电站中找到第一个x大于等于特工的核电站用左边5个和右边5个来更新答案。指向核电站的指针只会向右移。

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=100010;
pii a[N],b[N];
db dis(int i,int j)
{
	db res=(db)(b[i].fi-a[j].fi)*(b[i].fi-a[j].fi)+(db)(b[i].se-a[j].se)*(b[i].se-a[j].se);
	return sqrt(res);
}
void solve()
{
	int n;
	cin>>n;
	rep(i,0,n) cin>>a[i].fi>>a[i].se;
	rep(i,0,n) cin>>b[i].fi>>b[i].se;
	sort(a,a+n),sort(b,b+n);
	db ans=1e18;
	int k=0;
	rep(i,0,n){
		while(k<n&&a[k].fi<b[i].fi) ++k;
		rep(j,k-5,k+6) if(j>=0&&j<n) ans=min(ans,dis(i,j));
	}
	cout.setf(ios::fixed);
	cout<<setprecision(3)<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

可参考相似题目

平面上的最接近点对 - 洛谷

5.防线

牛客竞赛-防线

120. 防线 - AcWing题库

因为最多只有一个奇数点可以很容易算出来<=x所有数的和如果为奇数说明答案包含在这个区间里根据这个性质做二分。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=200010;
int n;
struct node{
	int s,e,d;
}T[N];
LL sum(int x)
{
	LL res=0;
	rep(i,0,n) if(T[i].s<=x) res+=(min(T[i].e,x)-T[i].s)/T[i].d+1;
	return res;
}
void solve()
{
	int l=0,r=0;
	cin>>n;
	rep(i,0,n) cin>>T[i].s>>T[i].e>>T[i].d,r=max(r,T[i].e);
	while(l<r){
		int m=l+r>>1;
		if(sum(m)&1) r=m;
		else l=m+1;
	}
	LL res=sum(l)-sum(l-1);
	if(res&1) cout<<l<<" "<<res<<endl;
	else cout<<"There's no weakness."<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

6.Corral the Cows

牛客竞赛-Corral the Cows

121. 赶牛入圈 - AcWing题库

将坐标离散化二维前缀和预处理出矩形包含点的个数。最后二分正方形的边长即可。

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=1010;
int c,n,s[N][N],mp[N];
pii p[N];
vector<int>vx,vy;
void disc(vector<int>&v)
{
	sort(all(v));
	v.erase(unique(all(v)),v.end());
}
int get(int x,vector<int>&v)
{
	return lower_bound(all(v),x)-v.begin();
}
bool che(int len)
{
	int px=0,py=0;
	rep(y,1,vy.size()){
		while(vy[y]-vy[py+1]+1>len) ++py;
		mp[y]=py;
	}
	rep(x,1,vx.size()){
		while(vx[x]-vx[px+1]+1>len) ++px;
		rep(y,1,vy.size()){
			py=mp[y];
			if(s[x][y]-s[px][y]-s[x][py]+s[px][py]>=c) return true;
		}
	}
	return false;
}
void solve()
{
	cin>>c>>n;
	vx.push_back(0),vy.push_back(0);
	rep(i,0,n){
		cin>>p[i].fi>>p[i].se;
		vx.push_back(p[i].fi),vy.push_back(p[i].se);
	}
	disc(vx),disc(vy);
	rep(i,0,n) ++s[get(p[i].fi,vx)][get(p[i].se,vy)];
	int h=max(vx.size(),vy.size());
	rep(i,1,h) rep(j,1,h) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
	int l=1,r=10000;
	while(l<r){
		int m=l+r>>1;
		if(che(m)) r=m;
		else l=m+1;
	}
	cout<<l;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

7.糖果传递

 122. 糖果传递 - AcWing题库

 牛客竞赛-糖果传递

[HAOI2008]糖果传递 - 洛谷

设ai对ai+1传递了xi个糖果xn为an给a1若xi取负值代表反向传递。目标就是求\sum_{i=1}^{n}\left | x_{i} \right |

的最小值。

设平均值为m可以列出以下等式

\left\{\begin{matrix} a_{1}+x_{n}-x_{1}=m\\ a_{2}+x_{1}-x_{2}=m \\ ... \\ a_{n}+x_{n-1}-x_{n}=m \end{matrix}\right.

把等式前i项加起来构成一个新的方程组

 \left\{\begin{matrix} a_{1}+x_{n}-x_{1}=m\\ (a_{1}+a_{2})+x_{n}-x_{2}=2m \\ ... \\ (a_{1}+a_{2}+...+a_{n})+x_{n}-x_{n-1}=(n-1)m \end{matrix}\right.

整理一下把x1~xn-1用xn表示

\left\{\begin{matrix} |x_{1}|=|a_{1}+x_{n}-m|\\ |x_{2}|=|(a_{1}+a_{2})+x_{n}-2m| \\ ... \\ |x_{n-1}|=|(a_{1}+...+a_{n-1})+x_{n}-(n-1)m| \\ |x_{n}|=|x_{n}| \end{matrix}\right.

发现只有xn一个变量问题转化成了货仓选址问题。 

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=1e6+10;
int a[N];
LL s[N];
void solve()
{
	int n,m;
	cin>>n;
	rep(i,1,n+1) cin>>a[i],s[i]=s[i-1]+a[i];
	m=s[n]/n;
	vector<LL>v(n,0);
	rep(i,1,n) v[i]=(LL)i*m-s[i];
	sort(all(v));
	LL x=v[n/2],ans=0;
	for(auto i:v) ans+=abs(x-i);
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

8.Soldiers  

123. 士兵 - AcWing题库

 x和y分开看y相同只要移到y的中位数即可。下面把x移成相邻的假设x排序后的序列为x_{1},x_{2},...,x_{n}移动后新的序列为a,a+1,a+2,...,a+n-1需要求|x_{1}-a|+|(x_{2}-1)-a|+...+|(x_{n}-n+1)-a|

的最小值把他看成一个新序列a就是取x_{1},x_{2}-1,...,x_{n}-n+1的中位数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=10010;
int x[N],y[N]; 
void solve()
{
	int n;
	cin>>n;
	rep(i,0,n) cin>>x[i]>>y[i];
	if(n==0){
		cout<<0;
		return;
	}
	sort(x,x+n),sort(y,y+n);
	rep(i,0,n) x[i]-=i;
	sort(x,x+n);
	int ans=0;
	rep(i,0,n) ans+=abs(y[i]-y[n/2])+abs(x[i]-x[n/2]);
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_; 
	while(_--){
		solve();
	}
	return 0;
}

9.NUMBER BASE CONVERSION 

牛客竞赛-NUMBER BASE CONVERSION

 124. 数的进制转换 - AcWing题库

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=200010;
map<char,int>mp;
map<int,char>mmp;
void init()
{
	for(char i='A';i<='Z';++i) mp[i]=i-'A'+10,mmp[i-'A'+10]=i;
	for(char i='a';i<='z';++i) mp[i]=i-'a'+36,mmp[i-'a'+36]=i;
	for(char i='0';i<='9';++i) mp[i]=i-'0',mmp[i-'0']=i;
}
void solve()
{
	int a,b;
	string s,ans;
	cin>>a>>b>>s;
	vector<int>v;
	per(i,s.size()-1,-1) v.push_back(mp[s[i]]);
	while(v.size()){
		int c=0;
		per(i,v.size()-1,-1){
			v[i]+=c*a;
			c=v[i]%b;
			v[i]/=b;
		}
		ans+=mmp[c];
		while(v.size()&&v.back()==0) v.pop_back();
	}
	reverse(all(ans));
	cout<<a<<" "<<s<<endl;
	cout<<b<<" "<<ans<<endl;
	cout<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	init();
	while(_--){
		solve();
	}
	return 0;
}

10. Cow Acrobats

牛客竞赛-Cow Acrobats

125. 耍杂技的牛 - AcWing题库

[USACO05NOV]奶牛玩杂技 - 洛谷

和国王的游戏哪个题几乎一样只不过改成加减法了。贪心策略是w+s升序排列。

可以用微扰法证明假设有w_{i}+s_{i}<=w_{i+1}+s_{i+1}sum为上面所有牛的重量和交换前局部的解为max(sum-s_{i},sum+w_{i}-s_{i+1})交换后解为max(sum-s_{i+1},sum+w_{i+1}-s_{i}).

为了方便比较所有值有加上s_{i}+s_{i+1}-sum就变成了

交换前max(s_{i+1},w_{i}+s_{i})

交换后max(s_{i},w_{i+1}+s_{i+1})

w_{i+1}+s_{i+1}>=w_{i}+s_{i}>=s_{i}交换后一定取w_{i+1}+s_{i+1}交换前不管是取哪个都不会比w_{i+1}+s_{i+1}大明显这种情况交换前更优。

最后要注意答案可能是负数。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=50010;
pii p[N];
bool cmp(pii a,pii b)
{
	return a.fi+a.se<b.fi+b.se;
}
void solve()
{
	int n;
	cin>>n;
	rep(i,0,n) cin>>p[i].fi>>p[i].se;
	sort(p,p+n,cmp);
	int s=0,ans=-2e9;
	rep(i,0,n) ans=max(ans,s-p[i].se),s+=p[i].fi;
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_; 
	while(_--){
		solve();
	}
	return 0;
}

11.To the Max

126. 最大的和 - AcWing题库

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=110;
int a[N][N];
void solve()
{
	int n,ans=-1e9;
	cin>>n;
	rep(i,1,n+1) rep(j,1,n+1) cin>>a[i][j],a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	rep(i,1,n+1) rep(j,1,n+1) rep(k,i,n+1) rep(z,j,n+1){
		int res=a[k][z]-a[k][j-1]-a[i-1][z]+a[i-1][j-1];
		ans=max(ans,res);
	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_; 
	while(_--){
		solve();
	}
	return 0;
}

12.Task 

127. 任务 - AcWing题库

关注获利公式和数据量y取最大所得到的获利都不如x取最小所以应该先满足x再考虑y。 

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=100010;
typedef long long ll;
typedef pair<int,int> P;
typedef multiset<int> MS;
P M[N],T[N];
MS ys;
int main()
{
	int m,t;
	while(scanf("%d%d",&m,&t)!=EOF){
		int cnt=0;
		ll ans=0;
		ys.clear();
		for(int i=0;i<m;++i) scanf("%d%d",&M[i].x,&M[i].y);
		for(int i=0;i<t;++i) scanf("%d%d",&T[i].x,&T[i].y);
		sort(M,M+m),sort(T,T+t);
		for(int i=t-1,j=m-1;i>=0;--i){
			while(j>=0&&M[j].x>=T[i].x) ys.insert(M[j].second),--j;
			MS::iterator it=ys.lower_bound(T[i].y);
			if(it!=ys.end()){
				++cnt;
				ans+=500*T[i].x+2*T[i].y;
				ys.erase(it);
			}
		}
		printf("%d %lld\n",cnt,ans);
	}
	return 0;
}

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：优雅地断开套接字连接

下一篇：解决numpy.core.

“算法进阶指南：第一章练习题” 的相关文章

concat函数在mySQL和Oracle中的不同1年前 (2023-02-02)
[一句话说iOS]dispatch如何造成死锁1年前 (2023-02-02)
Openmp Runtime 库函数汇总（上）1年前 (2023-02-02)
C++|变量1年前 (2023-02-02)
上周热点回顾（1.16-1.22）1年前 (2023-02-02)
__int128：懒人的福音1年前 (2023-02-02)
FPGA课程设计——数字电子时钟VERILOG（基于正点原子新起点开发板，支持8位或6位共阳极数码管显示时分秒毫秒，可校时，可设闹钟，闹钟开关，led指示）_fpga verilog课程设计1年前 (2023-02-02)
计算机网络——IP数据报的发送和转发过程1年前 (2023-02-02)
我辛辛苦苦做了一个月的项目，组长年底用来写了晋升PPT1年前 (2023-02-02)
WPF中使用WebView2控件1年前 (2023-02-02)

阿里云国际版