约翰有 N 头奶牛,他为这些奶牛准备了一个周长为 C 的环形跑牛场。所有奶牛从起点同时起跑,奶牛在比赛中总是以匀速前进的,第 i 头牛的速度为 Vi。只要有一头奶牛跑完 L 圈之后,比赛就立即结束了。
有时候,跑得快的奶牛可以比跑得慢的奶牛多绕赛场几圈,从而在一些时刻超过慢的奶牛。这就是最令观众激动的套圈事件了。请问在整个比赛过程中,套圈事件一共会发生多少次呢?
• 第一行:三个整数 N ,L 和 C,1 ≤ N ≤ 10^5; 1 ≤ L ≤ 25000; 1 ≤ C ≤ 25000
• 第二行到第 N + 1 行:第 i + 1 行有一个整数 Vi,1 ≤ Vi ≤ 10^6
单个整数:表示整个比赛过程中,套圈的次数之和
首先,如果一头牛跑的圈数比另一头牛多,那么它们的差值向下取整即为他们的收益,
容易想到\(O(n^2)\)的做法,枚举每头奶牛与其他奶牛的收益,但这样肯定超时
我们发现,对于一头牛跑的圈数\(cyl[i]\),只要找出所有比他小的值进行处理,
即\(Ans=\sum_{i=1}^nF[i], 且F[i]=\sum \bigg\lfloor cyl[i]-cyl[j]\bigg\rfloor,cyl[i]> cyl[j],1\leq i,j\leq n.\)
但这样好像也没用什么思路,
我们发现,其实\(cyl[i]-cyl[j]\)下取整是因为有小数,而不妨直接先把整数部分直接加起来,然后单独考虑小数部分(好吧也许很难想到)
我们发现,2个数的小数部分最多影响1,如果把cyl数组升序排序,那么Ans只要每次减去前面比当前小数部分小的count即可,
没错!发现变成了求逆序对,那么用树状数组或者归并排序即可
- #include < cstdio > #include < algorithm > #include < cmath > #define ll long long#define db double#define N 100010#define lowbit(x)((x) & ( - x)) using namespace std;
- const db eps = 1e-8;
- int n,
- v[N],
- L,
- C,
- p[N];
- ll cyl[N],
- Ans,
- m,
- tree[N];
- struct info {
- db num;
- int id;
- friend bool operator < (info a, info b) {
- return a.num < b.num;
- }
- }
- A[N];
- void add(int x) {
- for (; x <= n; x += lowbit(x)) tree[x]++;
- }
- ll sum(int x) {
- ll r = 0;
- for (; x; x -= lowbit(x)) r += tree[x];
- return r;
- }
- int main() {
- scanf("%d%d%d", &n, &L, &C);
- for (int i = 1; i <= n; ++i) scanf("%d", &v[i]);
- sort(v + 1, v + n + 1);
- db t = (db)(L * 1ll * C) / (db) v[n];
- for (int i = 1; i <= n; ++i) {
- cyl[i] = (ll)(t * v[i] / C);
- Ans += (i - 1) * cyl[i] - m;
- m += cyl[i];
- A[i].num = (db)(t * v[i] / C) - (db) cyl[i];
- A[i].id = i;
- }
- sort(A + 1, A + n + 1);
- int cnt = 0;
- for (int i = 1; i <= n; ++i) {
- if (! (fabs(A[i].num - A[i - 1].num) < eps) || i == 1)++cnt;
- p[A[i].id] = cnt;
- }
- for (int i = 1; i <= n; ++i) {
- Ans -= sum(n) - sum(p[i]);
- add(p[i]);
- }
- printf("%lld\n", Ans);
- return 0;
- }
来源: http://www.cnblogs.com/void-f/p/7780250.html