pythom 网站开发规范,为离职员工做的网站,创建自己的网页,还原wordpress题目链接:
D - 1D Country (atcoder.jp)
题目描述: 数据范围: 输入输出: 题目分析:
典型的l, r 区间问题#xff0c;即是前缀和问题#xff0c;但是注意到数据范围, 数据范围1e-9 到 1e9 数据范围#xff0c;要是从最小到最大直接for循环去模拟的话#xff0c;时间复杂度…题目链接:
D - 1D Country (atcoder.jp)
题目描述: 数据范围: 输入输出: 题目分析:
典型的l, r 区间问题即是前缀和问题但是注意到数据范围, 数据范围1e-9 到 1e9 数据范围要是从最小到最大直接for循环去模拟的话时间复杂度太高了O(2e9)注意到极限总共才2e5个居民要去想到映射不在关心他们的位置而去把下标转换为从1开始的然后在询问l, r这段区间的时候二分去查到对应的l, r他们映射后的位置然后用前缀和公式sum[映射后的r] - sum[映射后的l - 1]就是最后的答案但是我用map去写的时候卡到了最后一个数据但是用数组就过掉了why?
最后一个数据没过的代码:
#includebits/stdc.h
#define int long long using namespace std;const int N 2e5 10;mapint, intmp, ren, sum;
//mapint, intren;
int a[N];signed main() {int n, m;cin n;for(int i 1; i n; i ) {cin a[i];}for(int i 1; i n; i ) {int x;cin x;mp[a[i]] x;}
// sort(a 1, a n 1);//a[0] 0;
// sum[a[1] - 1] 0;sum[a[1]] mp[a[1]];for(int i 2; i n; i ) {sum[a[i]] sum[a[i - 1]] mp[a[i]]; }
// for(int i 1; i n; i ) {
// cout a[i] a[i] sum sum[a[i]] endl;
// }cin m;// 二分的是位置 while(m -- ) {int l, r;cin l r;// 二分第一个大于等于l的位置int ll 0, rr n 1;while(ll 1 rr) {int mid ll rr 1;if(a[mid] l) ll mid;else rr mid;}int st ll 1;// cout st st endl;// 二分最后一个小于等于r的位置 ll 0, rr n 1;while(ll 1 rr) {int mid ll rr 1;if(a[mid] r)ll mid;else rr mid;}int en ll;if(r a[n]) {en n;}if(l a[1]) {st 1;}
// cout st - 1 st - 1 endl;
// cout a[st - 1] a[st - 1] endl;
// cout en en endl;
// cout sumEnd sum[a[en]] endl;
// cout sumStart sum[a[st - 1]] endl;if(st 1) {cout sum[a[en]] endl;} else {cout sum[a[en]] - sum[a[st - 1]] endl;}}return 0;
}
/*
7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
1
-10 -4*/运行结果: 正确代码
#includebits/stdc.h
#define int long long using namespace std;const int N 2e5 10;int a[N], sum[N];signed main() {int n, m;cin n;for(int i 1; i n; i ) {cin a[i];}for(int i 1; i n; i ) {int x;cin x;sum[i] sum[i - 1] x;}cin m;// 二分的是位置 while(m -- ) {int l, r;cin l r;// 二分第一个大于等于l的位置int ll 0, rr n 1;while(ll 1 rr) {int mid ll rr 1;if(a[mid] l) ll mid;else rr mid;}int st ll 1;// cout st st endl;// 二分最后一个小于等于r的位置 ll 0, rr n 1;while(ll 1 rr) {int mid ll rr 1;if(a[mid] r)ll mid;else rr mid;}int en ll;cout sum[en] - sum[st - 1] endl; }return 0;
}运行结果:
