当前位置:网站首页>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;
}
边栏推荐
- kubeadm系列-00-overview
- Ecmascript6 introduction and environment construction
- Mengxin summary of LIS (longest ascending subsequence) topics
- Digital analog 1: linear programming
- MPSoC QSPI flash upgrade method
- Pytorch entry record
- Oracle advanced (III) detailed explanation of data dictionary
- Numpy 小坑:维度 (n, 1) 和 维度 (n, ) 数组相加运算后维度变为 (n, n)
- Mathematical modeling: factor analysis
- Business modeling of software model | vision
猜你喜欢
Run menu analysis
Redis实现高性能的全文搜索引擎---RediSearch
C [essential skills] use of configurationmanager class (use of file app.config)
Install the CPU version of tensorflow+cuda+cudnn (ultra detailed)
Guess riddles (11)
Halcon shape_ trans
猜谜语啦(8)
AUTOSAR从入门到精通100讲(103)-dbc文件的格式以及创建详解
Guess riddles (10)
容易混淆的基本概念 成员变量 局部变量 全局变量
随机推荐
Reasons for the insecurity of C language standard function scanf
Wechat H5 official account to get openid climbing account
Business modeling | process of software model
Guess riddles (2)
kubeadm系列-00-overview
Numpy pit: after the addition of dimension (n, 1) and dimension (n,) array, the dimension becomes (n, n)
Guess riddles (8)
Numpy 小坑:维度 (n, 1) 和 维度 (n, ) 数组相加运算后维度变为 (n, n)
资源变现小程序添加折扣充值和折扣影票插件
The combination of deep learning model and wet experiment is expected to be used for metabolic flux analysis
Search data in geo database
Basic number theory - factors
Guess riddles (142)
Ecmascript6 introduction and environment construction
猜谜语啦(7)
Use arm neon operation to improve memory copy speed
js异步错误处理
319. Bulb switch
AUTOSAR从入门到精通100讲(103)-dbc文件的格式以及创建详解
Array,Date,String 对象方法