当前位置:网站首页>Codeworks round 681 (Div. 2) supplement
Codeworks round 681 (Div. 2) supplement
2022-07-05 08:52:00 【Qizi K】
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;
}
边栏推荐
- Business modeling of software model | stakeholders
- Numpy 小坑:维度 (n, 1) 和 维度 (n, ) 数组相加运算后维度变为 (n, n)
- [formation quotidienne - Tencent Selection 50] 557. Inverser le mot III dans la chaîne
- ROS learning 4 custom message
- 轮子1:QCustomPlot初始化模板
- Solutions of ordinary differential equations (2) examples
- The location search property gets the login user name
- How apaas is applied in different organizational structures
- Run菜单解析
- Halcon blob analysis (ball.hdev)
猜你喜欢
[Niuke brush questions day4] jz55 depth of binary tree
How apaas is applied in different organizational structures
Guess riddles (9)
容易混淆的基本概念 成员变量 局部变量 全局变量
Install the CPU version of tensorflow+cuda+cudnn (ultra detailed)
Guess riddles (7)
Numpy pit: after the addition of dimension (n, 1) and dimension (n,) array, the dimension becomes (n, n)
猜谜语啦(6)
Hello everyone, welcome to my CSDN blog!
Guess riddles (5)
随机推荐
[formation quotidienne - Tencent Selection 50] 557. Inverser le mot III dans la chaîne
Dynamic dimensions required for input: input, but no shapes were provided. Automatically overriding
The combination of deep learning model and wet experiment is expected to be used for metabolic flux analysis
Halcon wood texture recognition
520 diamond Championship 7-4 7-7 solution
Halcon: check of blob analysis_ Blister capsule detection
猜谜语啦(4)
Halcon affine transformations to regions
Halcon clolor_ pieces. Hedv: classifier_ Color recognition
It cold knowledge (updating ing~)
资源变现小程序添加折扣充值和折扣影票插件
Latex improve
Numpy 小坑:维度 (n, 1) 和 维度 (n, ) 数组相加运算后维度变为 (n, n)
[daily training] 1200 Minimum absolute difference
Ecmascript6 introduction and environment construction
[daiy4] copy of JZ35 complex linked list
Pearson correlation coefficient
Tips 1: Web video playback code
Pytorch entry record
Guess riddles (11)