C. Inhabitant of the Deep Sea

2024-04-25 01:36
文章标签 deep sea inhabitant

本文主要是介绍C. Inhabitant of the Deep Sea,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本题链接:Problem - C - Codeforces

题目:

样例:

输入
6
4 5
1 2 4 3
4 6
1 2 4 3
5 20
2 7 1 8 2
2 2
3 2
2 15
1 5
2 7
5 2
输出
2
3
5
0
2
2

思路:

        数学+模拟。

        根据题意,一前一后的攻击,攻击k次后,总共击落舰队多少个。

        如果单纯模拟,肯定会TLE,所以要加上数学推导一下。

代码详解如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();signed main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;cin >> _t;while (_t--){solve();}return 0;
}
int n,x,k;
inline void solve()
{cin >> n >> k;deque<int>q;for(int i = 0;i < n;++i){cin >> x;q.emplace_back(x);}// 留最后一个判断是否能击落舰队while(q.size() > 1 and k){int mins = min(q.front(),q.back());// 这里 mins << 1 是平衡的,前后攻击一次,总攻击两次// 当 k 不符合前后攻击完一次,说明 k 会用完if(k < (mins << 1)){// 这里平分前后攻击的 k 次, k % 2 是判断最后一次攻击是否会回到前面q.front() -= (k >> 1) + (k % 2);q.back() -= (k >> 1);k = 0;	// 用完 k}else{// 前后攻击 mins 次q.front() -= mins;	q.back() -= mins;k -= (mins << 1);	// 总攻击 mins * 2 次}// 扫尾,如果击落舰队后,去除该舰队if(!q.front()) q.pop_front();if(!q.back()) q.pop_back();}int ans = n - q.size();	// 计算最后击落的舰队数量// 这里的 (q.size() and q.front() <= k) 是判断最后的一个舰队是否也可以击落cout << ans + (q.size() and q.front() <= k) << endl;
}

最后提交:

这篇关于C. Inhabitant of the Deep Sea的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/933381

相关文章

第二十二章 rust数据库使用:sea-orm详解

注意 本系列文章已升级、转移至我的自建站点中,本章原文为:rust数据库使用:sea-orm详解 目录 注意一、前言二、项目管理三、迁移文件四、实体文件五、业务使用 一、前言 只要开发稍微大型一点的项目,数据库都是离不开的。 rust目前并没有特别成熟的数据库框架,sea-orm这个框架是我目前所看到的成熟度最高的一个,并且仍在积极开发中。 所以本文将以sea-orm框

Deep Ocr

1.圈出内容,文本那里要有内容.然后你保存,并'导出数据集'. 2.找出deep_ocr_recognition_training_workflow.hdev 文件.修改“DatasetFilename := 'Test.hdict'” 310行 write_deep_ocr (DeepOcrHandle, BestModelDeepOCRFilename) 3.推理test.hdev

Introduction to Deep Learning with PyTorch

1、Introduction to PyTorch, a Deep Learning Library 1.1、Importing PyTorch and related packages import torch# supports:## image data with torchvision## audio data with torchaudio## text data with t

Face Recognition简记1-A Performance Comparison of Loss Functions for Deep Face Recognition

创新点 1.各种loss的比较 总结 很久没见到这么专业的比较了,好高兴。 好像印证了一句话,没有免费的午餐。。。。 ArcFace 和 Angular Margin Softmax是性能比较突出的

A fault diagnosis method of bearings based on deep transfer learning

A fault diagnosis method of bearings based on deep transfer learning 基于深度迁移学习的轴承故障诊断方法 ABSTRACT 近年来,许多深度迁移学习方法被广泛应用于不同工况下的轴承故障诊断,以解决数据分布移位问题。然而,在源域数据差异较大、特征分布不一致的情况下,深度迁移学习方法在轴承故障诊断中的准确率较低,因此本文提出了一种

Deep Learning Techniques for Medical Image Segmentation: Achievements and Challenges

前言: 该篇文章较为全面但稍偏简单的介绍医学图像分割的常见数据集、各种神经网络,以及常见的训练技巧等问题。 一、重点摘录 2.5D approaches are inspired by the fact that 2.5D has the richer spatial information of neighboing pixels wiht less computational costs t

Learning Policies for Adaptive Tracking with Deep Feature Cascades

Learning Policies for Adaptive Tracking with Deep Feature Cascades ICCV17 shotlight 作者:Chen Huang, CMU postdoctor,导师 Deva Ramanan summary 文章主要贡献在于速度与精度的权衡(AUC 0.638,fps 23),通过强化学习策略,来控制网络的深度,使得精度和

deep_thoughts

1.tensor tensor就是一个n维的数组。 import torchimport numpy as npdata = [[1, 2],[3, 4]]print(type(data))#<class 'list'>x_data = torch.tensor(data)print(type(x_data))#<class 'torch.Tensor'>print(x_data

java对象克隆之深度克隆 deep clone

克隆技术默认的是浅度克隆,对于包含在对象内部的对象并没有克隆,例如对象stdA包含对象x,克隆后得到对象stdB,也包含对象x,但两个x所指向的数据成员相同。 深度克隆实例如下: package com.demo;class Book implements Cloneable{private String name;private double price;public Book(Str

读Applying Deep Learning To Airbnb Search有感

读Applying Deep Learning To Airbnb Search有感 介绍 Airbnb的房屋预订系统对于房主和租客来说是一个双向的平台,房主想出租他们的空间,租客想预订房间。airbnb.com网站一开始是一个简单的根据一个特定的地理位置,召回一个酒店列表。 最初的搜索排序模型是人工评分的,后来梯度提升树(GBDT)代替了人工评分,这是房屋预订系统跨出的一大步,之后随之而来的