那里做直播网站,网页加速器,万网 网站 流程,网站建设木马科技Problem - E - Codeforces
E. Elevator
题意#xff1a;有一栋有m层的楼#xff0c;有n部电梯从1到m。第i个电梯再ai时刻上升。每一层有一个按钮#xff0c;可以让第一个到达该层的电梯停1秒#xff0c;如果有多个电梯同时到某一层#xff0c;下标靠前的被视为第一台到的…Problem - E - Codeforces
E. Elevator
题意有一栋有m层的楼有n部电梯从1到m。第i个电梯再ai时刻上升。每一层有一个按钮可以让第一个到达该层的电梯停1秒如果有多个电梯同时到某一层下标靠前的被视为第一台到的电梯。
现在要求第i个可以第一个到m层楼至少要按多少次按钮输出i为1到n的答案。
思路离线处理 树状数组
用arrayint,2或者PII存入ai和i值按照ai从小到大排序。按ai从小到大依次处理得到i的答案。
对于第i个下标来说答案就是前面处理的数量 乘以 当前ai 之后 减去 前面处理的aj之和再加上前面处理的下标在当前i前面的因为它们是ai - aj 1而在当前下标之后的是ai - aj。
注意第一层和第m层按电梯没有用
具体代码实现
#include iostream
#include vector
#include string
#include cstring
#include set
#include map
#include queue
#include ctime
#include random
#include sstream
#include numeric
#include stdio.h
#include functional
#include bitset
#include algorithm
using namespace std;// #define Multiple_groups_of_examples
#define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)-sync_with_stdio(false); // 开IOS需要保证只使用Cpp io流 *
#define dbgnb(a) std::cout #a a \n;
#define dbgtt cout !!!test!!! \n;
#define rep(i,x,n) for(int i x; i n; i)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pairint,int PII;const int INF 0x3f3f3f3f;
const int N 2e5 21;template class T
struct Fenwick { int n;vectorT a;Fenwick(const int n 0) : n(n), a(n, T()) {}void modify(int i, T x) {for (i; i n; i i -i) {a[i - 1] x;}}T get(int i) {T res T();for (; i 0; i - i -i) {res a[i - 1];}return res;}T sum(int l, int r) { // [l, r] *这里已经改过return get(r 1) - get(l);}int kth(T k) {int x 0;for (int i 1 __lg(n); i; i 1) {if (x i n k a[x i - 1]) {x i;k - a[x - 1];}}return x;}
};
void solve() {int n,m; cinnm;Fenwickint tr(n 1);vectorarrayint,2 sg(n);for(int i 1; i n; i) {cinsg[i-1][0];sg[i-1][1] i;}sort(all(sg));int sum 0;vectorint ans(n 1);for(int i 0; i n; i) {int id sg[i][1];int v sg[i][0];sum v;ans[id] (v * (i 1)) - sum tr.sum(1,id);tr.modify(id, 1);if(ans[id] m - 2) ans[id] -1;}for(int i 1; i n; i) coutans[i]\n;
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif{IOS;#ifdef Multiple_groups_of_examplesint T; cinT;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen(ANSWER.txt, w,stdout);#endif
}
