Codeworks round 681 (Div. 2) supplement

B. Saving the City

The question ：1 For bombs ,0 On behalf of the open space . Each time the bomb is detonated, it will be accompanied by the detonating coordinates +1&&-1 Bombs . Give a bomb (b) And light the bomb (a) The money needed , Ask for the minimum money to detonate all bombs .

tips: Must light a bomb . If the placement fee >= Ignition cost , Then it must not be placed ; conversely , Traverse from the beginning , Every time a new bomb is found , Compare (pos - lastpos - 1) * b And a, The former is a small bomb , On the contrary, ignite a new bomb .

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int t,n,a,b,len;
char boom[N];

int main(){
    
	cin >> t;
	while(t--){
    
		scanf("%d%d%s",&a,&b, boom + 1);
		len = strlen(boom + 1);
		int ans = 0, idx = 1;
		if(a <= b){
    
			while(idx <= len){
    
				while(boom[idx] == '0' && idx <= len)	idx ++;
				if(idx <= len)	ans += a;
				while(boom[idx] == '1' && idx <= len)	idx ++;
			}
		}else{
    
			int lastpos = 0;
			while(boom[idx] == '0' && idx <= len)	idx ++;
			if(idx <= len)	ans += a, lastpos = idx, idx++;
			while(idx <= len){
    
				//printf("idx = %d last = %d ans = %d\n", idx,lastpos,ans);
				while(boom[idx] == '1' && idx <= len)	idx ++, lastpos ++;
				while(boom[idx] == '0' && idx <= len)	idx ++;
				if(idx > len)	break;
				if((idx - lastpos - 1) * b <= a)	ans += (idx - lastpos - 1) * b;
				else	ans += a;
				lastpos = idx, idx++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

C. The Delivery Dilemma

The question ： The main points of n dish . You can pick up each dish by yourself , You can also take out . If you go by yourself, you must pick it up one by one , Takeout can be delivered directly to home . Ask for the shortest time to get n Time to order .

tips: Two points answer . Note that the minimum time is not necessarily taken in the takeout time .

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 200010;

int t,n;
struct node{
    
	int a, b;
}book[N];

int cmp(node n1, node n2){
     return n1.a < n2.a;}
 
bool check(ll x){
    
	ll sum = 0;
	for(int i = 1; i <= n; ++i){
    
		if(book[i].a <= x)	continue;
		else	sum += book[i].b;
	}
	return sum <= x;
}

int main(){
    
	cin >> t;
	while(t--){
    
		cin >> n;
		ll minn = 0;
		for(int i = 1; i <= n; ++i)	scanf("%d",&book[i].a);
		for(int i = 1; i <= n; ++i)	scanf("%d",&book[i].b), minn += (ll)book[i].b;
		sort(book + 1, book + 1 + n, cmp);
		
		if(minn <= book[1].a){
    
			printf("%lld\n", minn);
			continue;
		}
		ll ans = 0, l = book[1].a, r = book[n].a;
		while(l <= r){
    
			ll mid = l + r >> 1;
			if(check(mid))	ans = mid, r = mid - 1;
			else	l = mid + 1;
		}
		printf("%lld\n", ans);
	} 
	return 0;
}

D. Extreme Subtraction

The question ： Give a column number , There are two operations ：
A. front k Numbers each -1
B. after k Numbers each -1
k Take at will . Can they all become 0.

tips： greedy . The smaller the current number is, the better .

#include<bits/stdc++.h>

using namespace std;

const int N = 30010;

int t, n, a;

int main(){
    
	cin >> t;
	while(t--){
    
		scanf("%d",&n);
		int idx = 1, last = 1e9, tmp = 0;
		bool flag = true;
		for(; idx <= n; ++idx){
    
			scanf("%d", &a);
			if(last >= a)	last = a;
			else{
    
				tmp = last;
				last = a - last;
				break;
			}
		}
		for(idx ++; idx <= n; ++idx){
    
			scanf("%d", &a);
			if(a < last)	flag = false;
			else{
    
				tmp = min(a - last, tmp);
				last = a - tmp;
				//printf("tmp = %d last = %d\n", tmp,last);
			}	
		}
		(flag) ? puts("YES") :puts("NO");
	}	
	
	return 0;
}