2 条题解
-
1
# include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int a[N]; int n, m; int find(int x) { int l = 1; int r = n; int ret = -1; while (l <= r) { int mid = (l + r) / 2; if (a[mid] == x) { ret = mid; r = mid - 1; } else if (a[mid] > x) { r = mid - 1; } else { l = mid + 1; } } return ret; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } while (m--) { int x; scanf("%d", &x); printf("%d ", find(x)); } return 0; }
-
0
这里提供一种全新的线性做法,时间复杂度是 的。但是由于常数较大,被 的二分做法吊起来打。
我们用一个结构体存储每一个询问的位置及其询问的值。我们按照这个值排序,从而将问题转化为只有正数,使得我们可以搞一个指针,每一次询问暴力向右爬找到不小于询问元素的第一个元素,每次询问就可以做到均摊 了。
这种技巧在 P5073 里又一次出现,让每一次查询时间复杂度降到均摊 。
这种技巧在 P4118 里又一次出现,让每一次整块查询时间复杂度降到均摊 。
代码:(使用基数排序,保证线性时间复杂度)
#include <bits/stdc++.h> #define ptrdiff_t int #define size_t int char c; const size_t READ_MAXN = 1 << 15; const size_t READ_ARR_SIZE = READ_MAXN; const size_t WRITE_MAXN = 1 << 20; const size_t WRITE_ARR_SIZE = WRITE_MAXN; char inbuf[READ_ARR_SIZE], outbuf[WRITE_ARR_SIZE]; char *curinpos = inbuf + READ_MAXN, *curoutpos = outbuf; char *end_inbuf = inbuf + READ_MAXN, *end_outbuf = outbuf + WRITE_MAXN; inline char gc() { if (curinpos == end_inbuf) { end_inbuf = inbuf + fread(inbuf, 1, READ_MAXN, stdin); curinpos = inbuf; } return *curinpos++; } inline void pc(char x) { if (curoutpos == end_outbuf) { fwrite(outbuf, 1, READ_MAXN, stdout); curoutpos = outbuf; end_outbuf = outbuf + READ_MAXN; } *curoutpos++ = x; } inline void pc_unchecked(char x) { *curoutpos++ = x; } inline unsigned readuint() { unsigned eax(0); c = gc(); while (c < 48) c = gc(); while (c > 47) eax = (eax << 3) + (eax << 1) + (c & 15), c = gc(); return eax; } inline void putint(int x) { static char buf[15]; static int curpos; curpos = 0; do { buf[curpos++] = (x % 10) | 48; x /= 10; } while (x); while (curpos--) pc(buf[curpos]); } inline void putint_unchecked(int x) { static char buf[15]; static int curpos; curpos = 0; if (x < 0) { pc_unchecked('-'); x = -x; } do { buf[curpos++] = (x % 10) | 48; x /= 10; } while (x); while (curpos--) pc_unchecked(buf[curpos]); } struct question { int id; long long k; }; question* q; bool cmp(const question& a, const question& b) { return a.k < b.k; } // sort [q+l, q+r) inline void Sort(ptrdiff_t l, ptrdiff_t r) { if (r - l <= 1500) { std::sort(q + l, q + r, cmp); return; } long long *val = new long long[r - l + 5], *valt = new long long[r - l + 5]; for (ptrdiff_t i = l; i < r; i++) val[i - l] = valt[i - l] = q[i].k | ((1ll * i) << 32); ptrdiff_t *cnt = new ptrdiff_t[32768]; for (int i = 0; i < 30; i += 15) { memset(cnt, 0, 32768 * sizeof(ptrdiff_t)); for (ptrdiff_t j = 0; j < r - l; j++) ++cnt[(val[j] >> i) & 32767]; for (int j = 1; j < 32768; j++) cnt[j] += cnt[j - 1]; for (ptrdiff_t j = r - l - 1; ~j; j--) valt[--cnt[(val[j] >> i) & 32767]] = val[j]; memcpy(val, valt, (r - l + 5) * sizeof(long long)); } question* tmp = new question[r - l + 5]; for (ptrdiff_t i = l; i < r; i++) tmp[i - l] = q[i]; for (ptrdiff_t i = l; i < r; i++) q[i] = tmp[(val[i - l] >> 32) - l]; //delete[] val; //delete[] valt; //delete[] cnt; //delete[] tmp; } int *ans; int main() { ptrdiff_t curpos = 1; unsigned n = readuint(), m = readuint(); q = new question[m + 5]; int* ia = new int[n + 5]; ans = new int[m + 5]; for (unsigned i = 1; i <= n; i++) ia[i] = readuint(); long long minn = 0x3f3f3f3f; for (unsigned i = 0; i < m; i++) { q[i].id = i; q[i].k = readuint(); (q[i].k < minn) && (minn = q[i].k); } for (unsigned i = 1; i <= n; i++) ia[i] -= minn; for (unsigned i = 0; i < m; i++) q[i].k -= minn; Sort(0, m); for (int i = 0; i < m; i++) { while (curpos <= n && ia[curpos] < q[i].k) ++curpos; ans[q[i].id] = (ia[curpos] != q[i].k ? -1 : curpos); } for (unsigned i = 0; i < m; i++) putint_unchecked(ans[i]), pc_unchecked(' '); fwrite(outbuf, 1, curoutpos - outbuf, stdout); return 0; }
- 1
信息
- ID
- 1204
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 2
- 标签
- 递交数
- 34
- 已通过
- 17
- 上传者