2022美团校招技术岗笔试全部AC

为了切出更均匀的豆腐，想知道每一次下刀之后切出来的豆腐块中体积最大的那块有多大。

第一行两个整数n,m (1<=n,m<=1000)，代表最开始长宽高均为n厘米，总共切了m刀。
第二行m个小写字母，每个字母都是 x,y,z 中的一个。第i个代表刀垂直于哪个坐标轴。
第三行m个大于0且小于n的正整数。第i个代表第i刀所在平面到豆腐的右上角 (或者任选一个角并固定，无论选哪个角答案均相同) 的距离。
保证切的时候豆腐不会产生形变且不会产生位移。每次下刀都会把整块豆腐切开，不存在切到一半收刀，切出来的每块小豆腐都是边长为正整数的长方体。

输入

2 3

x y z

1 1 1

输出

4

2

1

#include 
using namespace std;
const int N = 1e5+10, M = 2e5+10;
int n, m;

int main() 
{
	cin >> n >> m;
	vector op(m+1);
	for(int i=1; i<=m; i++) cin>>op[i];
	vector v(m+1);
	for(int i=1; i<=m; i++) cin>>v[i];
	
	multiset x,y,z;
	x.insert(0), x.insert(n);
	y.insert(0), y.insert(n);
	z.insert(0), z.insert(n);
	
	for(int i=1; i<=m; i++) 
    {
		if(op[i][0]=='x')  x.insert(v[i]);
		else if(op[i][0]=='y')  y.insert(v[i]);
		else if(op[i][0]=='z')  z.insert(v[i]);
	}
	
	int mx=0, my=0, mz=0, pre=0;
	for(auto it:x)  mx = max(mx,it-pre), pre=it;
		pre=0;
	for(auto it:y)  my = max(mx,it-pre), pre=it;
		pre=0;
	for(auto it:z)  mz = max(mx,it-pre), pre=it;
	
	vector ans(m+1);
	for(int i=m; i>=1; i--) 
	{
		ans[i] = mx*my*mz;
		if(op[i][0]=='x') 
		{
			auto it = x.find(v[i]);
			int suf = *(++it);
			it--;
			int pre = *(--it);
			mx = max(mx, suf-pre);
			x.erase(v[i]);
		}
		if(op[i][0]=='y') 
		{
			auto it = y.find(v[i]);
			int suf = *(++it);
			it--;
			int pre = *(--it);
			my = max(my, suf-pre);
			y.erase(v[i]);
		}
		if(op[i][0]=='z') 
		{
			auto it = z.find(v[i]);
			int suf = *(++it);
			it--;
			int pre = *(--it);
			mz = max(mz, suf-pre);
			z.erase(v[i]);
		}
	}
	
	for(int i=1; i<=m; i++) 
		cout << ans[i] << endl;
	return 0;
}

给出一个长度为n的数组，进行m次数组上的区间 *** 作， *** 作包含将区间内所有数加上一个值和查询一个区间内所有数的和。如果允许重新排列初始数组中的元素并依次进行 *** 作，则 *** 作中所有查询区间和的答案之和能够达到多大?

输入 

第一行有两个数 n,m(1<=n=<5000,1<=m<=500)，代表数组长度和操作次数。第二行有n个数，代表初始数组中的元素，接下来m行每行 1 l r 或 2 l r k，分别代表查询下标属于 [l,r] 的元素之和这一揭作和将下标属于 [l,r] 的元素全部加上定值k。l r k 满足1<=l<=r<=n，1<=k<=5000

输出

输出若允许重新排列初始数组，进行m次 *** 作后产生的所有输出之和最大值

输入

5 5

3 4 2 1 5

1 1 3

2 3 4 2

1 2 4

2 2 3 2

1 3 5

输出

42

#include 
using namespace std;
const int N = 1e5+10, M = 2e5+10;
int n, m;

int main() {
	cin>>n>>m;
	vector a(n+1);
	for(int i=1; i<=n; i++) cin>>a[i];
	ll ans_sum=0;
	vector cnt(n+1),add(n+1);
	
	for(int i=1; i<=m; i++) {
		int op; cin>>op;
		if(op==1) {
			int l,r;
			cin>>l>>r;
			for(int i=l; i<=r; i++) cnt[i]++, ans_sum += add[i];
		}
		else{
			int l,r,k;
			cin>>l>>r>>k;
			for(int i=l; i<=r; i++) add[i] += k;
		}
	}
	
    sort(a.begin()+1,a.end());
    sort(cnt.begin()+1,cnt.end());
    
    for(int i=1; i<=n; i++) 
    	ans_sum += 1LL * cnt[i] * a[i];
	cout << ans_sum << endl;
	return 0;
}

 OVER~