目录
栈的min
外卖递送
奇偶序列
sort
五彩斑斓的世界
括号家族
名次并列
栈间
双端队列
合并货物
逆序对
活动分组
栈的min
难度:黄金巴 占用内存:128 M时间限制:1秒
小码哥又被安排任务了，这次他需要要设计一个堆栈，他除了可以满足正常的栈的操作以外，还要可以输出栈内最小元素值。
o(n)的算法小码哥当然会，小码哥为了给上司一个惊喜决定设计一个o(1)就能输出的程序，自然这个任务就被丢给你了。
c(x)-将元素x插入栈中y()-移除栈顶元素
s()-得到栈顶元素
g_m()-得到栈中最小元素
//
// Created by abner on 2024/5/23.
//
#include <bits/stdc++.h>
using namespace std;
stack<int>stackValue;
stack<int>stackMin;
void push(int x){
stackValue.push(x);
if (stackMin.empty() || stackMin.top()>=x)
stackMin.push(x);
}
void pop(){
if (stackMin.top()==stackValue.top())
stackMin.pop();
stackValue.pop();
}
int top(){return stackValue.top();}
int getMin(){return stackMin.top();}
int main(){
int n;
cin >> n;
while (n--){
int a;
cin >> a;
switch (a){
case 1:
int x;
cin >> x;
push(x);
break;
case 2:
pop();
break;
case 3:
cout <<top()<<endl;
break;
case 4:
cout <<getMin()<<endl;
break;
}
}
return 0;
}
外卖递送
难度:黄金时间限制:1秒巴:占用内存:64 M
小码哥又被安排去建设外卖站了，所有居民的居住地点a;都在一条x轴上，小码哥为了使送外卖移动的距离最短，现在在选择设置外卖站的位置。
小码哥请你帮忙计算把站建在何处，可以使得站到每家居民的距离之和最小?
注意:不保证居民的居住地点a;唯一，即可以两个居民的居住地点相同，允许外卖站设在居民点。
格式
输入格式:第一行一个整数n，表示居民的居住地点个数;第二行 n 个整数 a1 ~ an 。
输出格式:输出束冬娄女表示距离之和的最小值
#include<bits/stdc++.h>
using namespace std;
int n1[100005],n2[100005];
int main(){
int n;
long long sum=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>n1[i];
sort(n1,n1+n);
for(int i=n-1;i>=0;i--){
n2[n-1-i]=n1[i];}
for(int i=0;n1[i]<n2[i];i++)
sum+=n2[i]-n1[i];
cout<<sum<<endl;
return 0;
}
奇偶序列
难度:黄金
巴 占用内存:128 M时间限制:1秒
给定几个数的数组，奇数和偶数分别排序(即所有奇数的占位和偶数的占位不变)
格式
输入格式:输入一个正整数n;
第二行输入 n 个数 ai。
输出格式:输出排好序的数组。
#include<bits/stdc++.h>
using namespace std;
const int MAX = 10005;
int ary[MAX];
// 选择法排序
// 此函数将根据 flag 的取值分别对奇、偶数位上的数字进行排序：保持奇数和偶数的占位不变
// flag=true 时对奇数位执行排序
// flag=false 时对奇数位执行排序
void sortSubjectOdd(int ary[], int aryLen, bool flag)
{
int pos;
// 根据 flag 的取值进行排序：
for(int i=0;i<aryLen-1;i++){
if((ary[i] & 1) == flag) pos = i;
else continue;
// 选择排序
for(int j=i+1;j<aryLen;j++){
if(((ary[j] & 1) == flag) && (ary[j] < ary[pos]))
pos = j;
}
// 不等则发生交换
if(pos != i) swap(ary[i], ary[pos]);
}
}
void sortRespectively(int ary[], int aryLen){
// 对偶数排序
sortSubjectOdd(ary,aryLen,false);
// 对奇数排序
sortSubjectOdd(ary,aryLen,true);
}
// 打印数组内容
void printArt(int ary[], int aryLen) {
for(int i=0;i<aryLen;i++) cout<<ary[i]<<" ";
}
int main( )
{
// 获取输入
int n;cin>>n;
for(int i=0;i<n;i++) cin>>ary[i];
// 处理数据
sortRespectively(ary,n);
// 执行输出
printArt(ary,n);
return 0;
}
sort
乡难度:黄金
时间限制:1秒巴: 占用内存:128 M
或许在某个平行宇宙，会存在一种语言，使用的字母和英语一样，但字典序不一样给出1个字典序和1个字符串，将字符串按新字典序排序。
格式
输入格式:第一行26个互不相同的小写字母，表示新型字典序;第二行1个字符串，表示待排序字符串。
输出格式:1个字符串代表答案。
#include<bits/stdc++.h>
using namespace std;
// 定义字典序的总长度
const int N=26;
const int MAX = 100005;
char dict[N];
char str[MAX];
void sortStr(char str[], char dict[])
{
// 获取输入字符串的长度
int strLen = 0, pos = 0;
while(str[strLen]) strLen++;
// 扫描字典序
for(int i=0; i<N;i++){
// 扫描给定字符串（逆序）
for(int j = strLen-1; j>=pos; j--){
// 判断当前字符是否与字典序中的当前字符一致，是就需要考虑与前面的字符交换位置
if(str[j] == dict[i]){
// 若待交换位置的字符与当前字符一致，则待交换位置后移
while(pos<j && str[pos] == dict[i]) pos++;
// 发生交换
swap(str[j],str[pos++]);
}
}
// 判断前向指针是否已经走到给定字符串的尽头
if(pos == strLen) break;
}
}
int main( )
{
// 获取输入
cin>>dict;
cin>>str;
// 处理数据
sortStr(str,dict);
// 执行输出
cout<<str;
return 0;
}
五彩斑斓的世界
乡难度:钻石时间限制:1秒巴 占用内存:128 M
小码哥是一个喜欢字符串的男孩子。
小码哥现在有一个字符集为al()的字符串，他想要对这个字符串进行化简，具体规则如下:
1.一个纯串无法被化简;a
2.一个由|分隔的串，可以化简为| 两侧较长的一个:如可化简为alaaaa3.一个带有()的串，化简时先化简括号内的串。
由于小码哥忙于他的研究，化简这个字符串的重任被交到了你的身上。
#include<bits/stdc++.h>
using namespace std;
void Simplification(string str)
{
stack<int> s;
int strLen = 0, strLenMax, tmp;
// 遍历字符串以将 a|() 串变为仅由 | 划分的数字串（此时,用数字 -1 表示分隔符 | ）
for(int i=0; str[i]; i++){
// 若遇到正括号，则需要对当前的字符串长度统计结果进行暂存，以进行新的统计
if(str[i] == '('){
s.push(strLen);
// 重置字符串统计变量
strLen = 0;
// 正括号阻断标记
s.push(-2);
}
// 若遇到分隔符，则需要对当前的字符串长度统计结果进行暂存（便于之后进行对比）
else if(str[i] == '|'){
s.push(strLen);
// 重置字符串统计变量
strLen = 0;
// 分隔符阻断标记
s.push(-1);
}
// 若遇到反括号，则需要对当前一段由括号框起来的字符串进行处理
else if(str[i] == ')'){
// 首先将当前统计的长度入栈
s.push(strLen);
// 处理当前反括号匹配的正括号之间的数据
strLen = strLenMax = 0;
while(1){
// 将栈的顶部元素出栈
tmp = s.top();
s.pop();
// 若该元素为分隔符，则需要将其与前面的字串长度进行对比，并取最大值。如“aa|aaa|a|aa”
if(tmp == -1){
strLenMax = max(strLen, strLenMax);
strLen = 0;
}
// 若该元素为正括号，则需要比较更前面的字符串长度
else if(tmp == -2){
strLenMax = max(strLen, strLenMax);
s.push(strLenMax);
strLen = 0;
break;
}
// 若该元素不为分隔符或正括号，则取出当前长度
else strLen += tmp;
}
}
// 否则记当前字符串长度 +1
else strLen++;
}
// 为循环结束时最后记录的纯 a 串长度进行保存
s.push(strLen);
// 接下来需要将栈中的所有数据进行汇总处理（此步骤执行时，栈内无括号，仅含分隔符）
strLen = strLenMax = s.top();
s.pop();
while(!s.empty()){
tmp = s.top();
s.pop();
if(tmp != -1) strLen += tmp;
else{
strLenMax = max(strLen, strLenMax);
strLen = 0;
}
}
// 打印最大值
cout<<max(strLen, strLenMax);
}
int main( )
{
string str;
// 获取输入
cin>>str;
// 对字符串进行化简并打印化简后的长度
Simplification(str);
return 0;
}
括号家族
难度:钻石时间限制:1秒巴 占用内存:128 M
小码哥在研究只有左括号和右括号组成的序列。给出一个括号序列，求出最长合法子串和它的数量(合法的定义:这个序列中左右括号匹配)。
例如:(()不合法，)()(也不合法，但()()和(())合法。
格式
输入格式:输入一行只有左括号和右括号组成的序列(只包含小括号)
输出格式:输出两个数字:最长子字符串的长度，以及此类子字符串的数量，如果没有这样的子字符串，则输出 01 。
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x & (-x))
int a[N];
int main() {
std::ios::sync_with_stdio(false);
string s;
cin >> s;
stack<int> st;
int l = s.length();
for (int i = 0; i < l; i++) {
if (s[i] == '(')
st.push(i);
else {
if (st.size())
a[st.top()] = a[i] = 1, st.pop();
}
}
int mx = 0, cnt = 0;
map<int, int> mp;
for (int i = 0; i < l; i++) {
if (a[i]) {
cnt++;
} else {
if (cnt >= mx) {
mx = cnt;
mp[mx]++;
}
cnt = 0;
}
}
if (cnt >= mx) {
mx = cnt, mp[mx]++;
}
if (mx == 0)
mp[mx] = 1;
cout << mx << " " << mp[mx] << endl;
return 0;
}
名次并列
难度:钻石时间限制:1秒巴 占用内存:128 M
有几个人参加比赛，其中分数排名前k的人将被选入下一轮(选入下一轮的人分数必须为正)，特别的，如果几个人分数相同且刚好并列处于第k名(或是并列k-i名，但是全部算入后选入下一轮的人数超过k人)，这几个人都将被选入下一轮。
小码哥请你输出进入下一轮的人数?
格式
输入格式:输入一共两行，第一行是两个数n,k(1≤k≤n≤1e5);第二行有 几 个数，分别参加比赛的人的分数 a1,a2,...,an(0≤ ai< 100 )。
输出格式:输出进入下一轮的人数。
#include<stdio.h>
#include<stdlib.h>
#define N 100007
int n,k,a[N],ans; // 定义变量n、k、a、ans，其中a为数组，N为数组大小的最大值
int cmp(const void *a, const void *b) { // 快速排序函数定义
int x=*(const int*)a,y=*(const int*)b; // 强制类型转换，将指针a和指针b转换成整数类型，并赋值给x和y
if(x>y)
return -1; // 如果x>y，则返回-1
else if(x<y)
return 1; // 如果x<y，则返回1
else
return 0; // 否则返回0
}
int main()
{
scanf("%d%d",&n,&k); // 输入n和k的值
for(int i=1;i<=n;i++)
scanf("%d",&a[i]); // 输入n个数并存储到数组a中
qsort(a+1,n,sizeof(int),cmp); // 使用快速排序函数对数组a进行降序排列
for(int i=1;i<=k;i++){ // 遍历前k个数
if(a[i]>0)
ans++; // 如果第i个数大于0，则计数器加1
else
{
printf("%d",ans); // 否则输出计数器的值，并结束程序
return 0;
}
}
for(int i=k+1;i<=n;i++) // 遍历剩余的数
if(a[i]==a[k])
ans++; // 如果第i个数和第k个数相等，则计数器加1
printf("%d",ans); // 输出计数器的值，并结束程序
return 0;
}
栈间
少 难度:黄金@ 时间限制:1秒巴占用内存:128 M
小码哥用STL的stack容器创建了一个栈，但这个容器不能从中间访问。现在他想创建一个能从中间访问的“栈”，请你协助编写一个。
新的栈能实现以下操作:
1x//将整数x压入栈
2 //输出栈顶元素
3 i //输出栈的第i个元素(从0数起)
4 /弹出栈顶元素
这个栈一开始是空的。
#include <bits/stdc++.h>
#define ll long long
#define DEBUG 112412
using namespace std;
const int maxn = 5e6 + 55;
int a[maxn];
int main(){
#if DEBUG==1
freopen(“1”,”r”,stdin);freopen(“2”,”w”,stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int cnt = 0;
int n;
cin >> n;
for (int i = 1; i <= n; ++i){
int op;
cin >> op;
if (op == 1){
int x;
cin >> x;
a[++cnt] = x;
}
else if (op == 2){
cout << a[cnt] << '\n';
}
else if (op == 3){
int x;
cin >> x;
cout << a[x + 1] << '\n';
}
else{
cnt--;
}
}
}
双端队列
难度:黄金时间限制:1秒巴 占用内存:128 M
小码哥想创建一个双端队列，即，两头都能进，两头都能访问，两头都能出。请你创建一个这样的双端队列并帮他实现以下操作:
1x//将整数x增加到头部
2x//将整数x增加到尾部
3 //访问头部的元素
//访问尾部的元素D
幼//弹出(删除)头部的元素
6//弹出(删除)尾部的元素
这个双端数列一开始是空的。
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000005;
int s[MAX];
deque<int> q;
int main( )
{
int n, opt, num; cin>>n;
// 执行 n 次查询
while(n--){
scanf("%d", &opt);
switch(opt){
case 1:
cin>>num;
q.push_front(num);
break;
case 2:
cin>>num;
q.push_back(num);
break;
case 3:
cout<<q.front()<<endl;
break;
case 4:
cout<<q.back()<<endl;
break;
case 5:
q.pop_front();
break;
case 6:
q.pop_back();
break;
}
}
return 0;
}
合并货物
难度:黄金 时间限制:1秒巴 占用内存:128 M
小码哥又被派来合并货物了，最近公司接受了一大笔货物，现在已经按照不同的种类分成许多堆，相同种类的货物在同一堆，小码哥决定把他们合并来方便运输。
每一次合并，小码哥可以把两堆货物合并到一起，消耗的体力等于两堆货物的重量之和。可以看出，所有的货物经过几-1次合并之后，就只剩下一堆了。小码哥在合并货物时总共消耗的体力等于每次合并所耗体力之和。
因为小码哥不可以耗费太多的体力来干这种事情，所以小码哥在合并货物时要尽可能地节省体力。这些货物的重量都为一，并且小码哥知道货物的种类和数目，小码哥想知道他至少需要花费多少体力来解决这个问题。(小码哥可以合并任意两堆货物)
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define N 110000
ll c[N] ;
struct op{
ll v;
}s[N];
priority_queue<op> q;
bool operator < (const op &a , const op &b){
return a.v > b.v ;
}
int main(){
ll n;
cin >> n;
ll ans = 0 ,all = 0;
for (int i = 1; i <= n; i++){
cin >> c[i] ;
op f ;
f.v = c[i] ;
q.push(f) ;
}
while (q.size() != 1){
op f = q.top();
q.pop();
op g = q.top() ;
q.pop();
ans = ans + f.v + g.v ;
op h ;
h.v = f.v + g.v ;
q.push(h) ;
}
cout << ans ;
return 0;
}
逆序对
少 难度:钻石◎时间限制:1秒巴占用内存:128 M
给你一个长度为n的序列，有m 次操作。每次翻转,”的区间，每次操作后询问序列逆序对个数的奇偶性。
格式
输入格式:第一行1个正整数，为原序列的长度 n;
第二行 n 个自然数，表示该序列的元素 ai;
第三行1个正整数，为操作次数 m;
接下来 m 行，每行两个整数 l,r，表示翻转的区间。
输出格式: m 行，每行表示每次问询的结果。
#include<iostream>
using namespace std;
int n,nums[10010],temp[10010],tree[10010];
int lowbit(int x){
return x&-x;
}
void add(int x,int t){
for(;x<=n;x+=lowbit(x)){
tree[x]+=t;
}
}
int get(int x){
int res=0;
for(;x>0;x-=lowbit(x)){
res+=tree[x];
}
return res;
}
void MergeSortArr(int arr[],int left,int mid,int right){//该函数同于将两个有序列合并成一个有序列，同时当两个有序列都为同一个元素是一样可以处理
int i = left,j = mid + 1;//两个索引用来遍历两个有序列
int k=0;//k用来遍历暂存数组temp
int temp[right-left+1];//开一个数组暂时存放
while(i <=mid && j <= right){//对两个有序列进行遍历排序，有一个序列遍历完成结束循环
if(arr[i] < arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while(i <= mid){//将另外一个没有遍历完全的有序列全部插入到temp中
temp[k++] = arr[i++];
}
while(j <= right){
temp[k++] = arr[j++];
}
//！！这里需要注意循环的条件里面不能使用left因为left的值在改变
for(i = 0;i < k;i++)//将排好序的序列更新到目标数组中
arr[left++] = temp[i];
}
//递归方法
void MergeSort(int arr[],int left,int right){
if(left == right)//如果两个划分为同一元素，递归结束
return ;
int mid = (left + right) / 2;//对本个划分再次进行划分
MergeSort(arr, left, mid);//对左边的序列进行划分此条命令结束代表左边的序列已经有序
MergeSort(arr, mid+1, right);//对右边的序列进行划分此条命令结束代表右边的序列已经有序
MergeSortArr(arr, left, mid, right);//和并两个序列
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>nums[i];
temp[i] = nums[i];
}
MergeSort(temp,1,n+1);
int cnt = 0;
for(int i=1;i<=n;i++){
int idx = lower_bound(temp+1, temp+n+1, nums[i])-temp;
add(idx,1);
cnt+= i-get(idx);
}
bool isOdd = cnt&1;
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
cnt = (r-l)*(r-l+1)/2;
isOdd ^= cnt&1;
cout<<(isOdd ?"even":"odd")<<endl;
}
}
活动分组
少难度:黄金时间限制:1秒四占用内存:128 M
小码哥组织一次团建活动，共有人参加。活动分为A、B两个项目，每个项目都需要两人组队参加。假设每个人有两个能力值a，6 分别表示对 A、B两个项目的擅长程度，为了使活动圆满进行，小码哥希望每一组的两个人A能力值之和等于B能力值之和。请你帮忙计算是否有一种分组的可能满足小码哥的想法。
格式
输入格式:输入共三行，第一行一个偶数 n€[2,1 x105]表示总人数;第二行 n 个正整数表示每个人 A 项目的能力值;第三行 n个正整数表示每个人 B 项目的能力值。
输出格式:一行，如果存在这样的分组输出否则输出YESNO
/*
活动分组
思路：对每个人而言，他的 A、B 能力之差应与其匹配对象的 A、B 能力之差互反
*/
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100005;
int capacity[MAX][2];
int capacityGap[MAX];
bool matchAntithesis(int ary[][2], int len)
{
// 计算每个人的能力数组中，第一个元素与第二个元素的差值
for(int i=0;i<len;i++) capacityGap[i] = ary[i][0]-ary[i][1];
// 对差值数组排序
sort(capacityGap,capacityGap+len);
// 执行消融
int l = 0, r = len-1;
while(l<r){
if(capacityGap[l] + capacityGap[r] == 0){
l++;
r--;
}
else return false;
}
return true;
}
int main( )
{
// 录入数据
int n;cin>>n;
for(int i=0;i<2;i++)
for(int j=0;j<n;j++) cin>>capacity[j][i];
// 执行匹配
if(matchAntithesis(capacity,n)) cout<<"YES";
else cout<<"NO";
return 0;
}
