AcWing 1996. 打乱字母(贪心+二分)
2022/1/26 23:34:46
本文主要是介绍AcWing 1996. 打乱字母(贪心+二分),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
https://www.acwing.com/problem/content/1998/
思路
我们开四个string数组,然后前两个分别存储的是升序字符串序列和降序字符串序列,然后第三四个同理,然后对前两个进行sort排序,排完序后我们根据之前的c、d数组对a、b数组进行二分搜索,当然可以直接使用lowerbound或者upperbound,当然也可以自己手写,我这里直接用的STL,详情请看代码
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000009 #define endl "\n" #define PII pair<int,int> ll ksm(ll a,ll b) { ll ans = 1; for(;b;b>>=1LL) { if(b & 1) ans = ans * a % mod; a = a * a % mod; } return ans; } ll lowbit(ll x){return -x & x;} const int N = 1e5+10; string a[N],b[N],c[N],d[N]; int main() { int n; cin>>n; for(int i = 0;i < n; ++i) { cin>>a[i]; sort(a[i].begin(),a[i].end());//a存储的是升序字典序的字符串序列 c[i] = a[i]; b[i]=a[i]; reverse(b[i].begin(),b[i].end());//b存储的是降序字典序的字符串序列 d[i] = b[i]; } sort(a,a+n); sort(b,b+n); for(int i = 0;i < n; ++i) { int l = lower_bound(b,b+n,c[i]) - b + 1;//因为我们想寻找的是大于等于的位置,所以需要加一 int r = upper_bound(a,a+n,d[i]) - a;//我们寻找的位置是大于d的第一个位置,所以不需要我们认为的加一 cout<<l<<" "<<r<<endl; } return 0; }
这篇关于AcWing 1996. 打乱字母(贪心+二分)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享