E Add and Mex（調和級數 暴力）
題意：
? 給出一個長度為n\(\le 1e5\)的陣列a，每秒對陣列中的數加上其下標，例如\(a_i\)在第一秒為\(a_i+i\)，第二秒為\(a_i+2i\)，請輸出前m\(\le 1e5\)秒中每一秒的最小的非負整數，
思路：
? 因為只有n個數，那么這個最小非負整數一定小于\(1e5\)，那么當\(a_i\)大于1e5的時候就沒有用了，這點很重要，那么我們直接去暴力列舉，把結果存在\(vector<int> flag[秒數]\)中，這個復雜度是調和級數也就是\(O(nlogn)\)的，輕松可以跑過，但是要注意的是，很可能會出現全是-1e9的極端情況，那你列舉的秒數的起點就需要對于這一點作出特判，詳情看代碼，
實作：
const int N = 200005;
int n, m;
int a[N];
vector<int> flag[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
if(a[i] > n) continue;
int st;
if(a[i] < 0)
st = (abs(a[i]) / i);
else
st = 1;
for(int j = st; j <= m; j ++)
{
if(a[i] + j * i < 0) continue;
if(a[i] + j * i > n) break;
flag[j].push_back(a[i] + j * i);
}
}
for (int i = 1; i <= m; i++)
{
vector<bool> vis(N, 0);
for(auto x : flag[i])
if(x < N)
vis[x] = 1;
int res = 0;
while(vis[res])
res ++;
cout << res << '\n';
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511962.html
標籤：其他