G. Old Floppy Drive (math、二分)

淩亂°似流年 2021-07-16 23:11 217阅读 0赞

[题目][Link 1]

思路：  
失败的情况：n个数全部相加一遍总和<=0,且前缀和的最大数max也比所询问的数x小

成功的情况：因为询问的次数较多，用二分查找优化，先创造个二分的递增条件

对于能在一个循环就找到符合条件的答案 x<=max(上文提及)  
模拟一下过程，3 -2 2 -1 5 4 -3 , 前缀和： 3 1 3 2 7 11 8 如果x=7 要用二分找出第一个>=7的数所在位置，可以知道对于3后面的那个1来说前面的3已经小于7了，1比它小也不可能大于所以这个1是无效的，只有出现>3的数才有可能大于等于7，所以我们令1变为3去维护一个非递减数列，同理2变为3，8变为11.  
新的用于二分的数列化为 ：3 3 3 3 7 11 11，然后直接二分得位置，位置-1即为答案。

不能在一个循环找到答案  
每一次循环会增加sum（n个数和），当我们先循环c=(x-max+sum-1)/sum次，然后再二分找到还剩下需要相加的数即可。ans=n*c+lower\_bound(lst+1,lst+1+n,x-c*sum)-1。

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int Mod = 1e9 + 7;
    ll lst[Max];
    ll mm[Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, m;cin >> n >> m;
    		ll ma = 0, sum = 0;
    		for (int i = 1;i <= n;i++)
    		{ 
    			cin >> lst[i];
    			sum += lst[i];
    			ma = max(ma, sum);
    			mm[i] = ma;
    		}
    		for (int k = 1;k <= m;k++)
    		{ 
    			ll a;cin >> a;
    			if (a > ma && sum <= 0)cout << -1 << " ";
    			else if (a <= ma)
    			{ 
    				int ans = lower_bound(mm + 1, mm + 1 + n, a) - mm - 1;
    				cout << ans << " ";
    			}
    			else
    			{ 
    				ll ans = -1;
    				ll k = max((ll)0,(a - ma + sum - 1) / sum);
    				ans += n * k;
    				a -= k * sum;
    				ans += lower_bound(mm + 1, mm + 1 + n, a) - mm;
    				cout << ans << " ";
    			}
    		}
    		cout << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1490/problem/G