define i++ push 函数类 tdi lose lambda 表达式 back
这次套路深啊,怎么还有改错题!。
上来看题,每个题目的输入数据都很大,果断上 scanf,printf, 千万不能用 cin,cout
1. 右上角的点,我的思路是先对每一行去重(题目好像说没有重的点耶!),每一行只有最右边的点才是候选点,然后对这些候选点按照 y 坐标,从大到小访问,要求相应的 x 是严格递增的,最后打印输出。
- #include < bits / stdc++.h > #define pb push_back typedef long long ll;
- using namespace std;
- typedef pair < int,
- int > pii;
- const int maxn = 1e3 + 10;
- int n;
- void solve() {
- map < int,
- int > ma;
- scanf("%d", &n);
- int x,
- y;
- for (int i = 0; i < n; i++) {
- scanf("%d%d", &x, &y);
- if (ma.count(y)) {
- ma[y] = max(ma[y], x);
- } else ma[y] = x;
- }
- vector < pii > res;
- auto it = ma.rbegin();
- x = it - >second - 1;
- //cout << it->first <<endl;
- while (it != ma.rend()) {
- if (it - >second > x) {
- res.pb({
- it - >second,
- it - >first
- });
- x = it - >second;
- }
- it++;
- }
- for (pii t: res) {
- printf("%d %d\n", t.first, t.second);
- }
- }
- int main() {
- freopen("test.in", "r", stdin);
- //freopen("test.out", "w", stdout);
- solve();
- return 0;
- }
2. 我认为是分治, 首先考虑数组的最小值,哪些区间可以取到取小值,取到最小值,使得结果最大,当然是和最大,那就是全部的数,接下来这个最小值就可以不考虑了,分别对左半和右半重复上面处理。
- #include < bits / stdc++.h > #define pb push_back typedef long long ll;
- using namespace std;
- typedef pair < int,
- int > pii;
- const int maxn = 5e5 + 10;
- int n;
- ll a[maxn];
- ll s[maxn];
- ll f(int x, int y) {
- return s[y] - s[x - 1];
- }
- ll res = 0;
- void work(int x, int y) {
- if (x > y) return;
- if (x == y) {
- res = max(res, a[x] * a[x]);
- return;
- }
- int p = x;
- for (int i = x; i <= y; i++) {
- if (a[i] < a[p]) {
- p = i;
- }
- }
- res = max(res, a[p] * f(x, y));
- work(x, p - 1);
- work(p + 1, y);
- }
- void solve() {
- scanf("%d", &n);
- for (int i = 1; i <= n; i++) {
- scanf("%lld", &a[i]);
- s[i] = s[i - 1] + a[i];
- }
- work(1, n);
- printf("%lld\n", res);
- }
- int main() {
- freopen("test.in", "r", stdin);
- //freopen("test.out", "w", stdout);
- solve();
- return 0;
- }
3. 题目描述的挺复杂,就是多个角度的优先队列,然后就试了试刚学习的函数类(仿函数,函数对象,函数指针),以及 lambda 表达式,写了一下。
最后过了 80%, 我的是按时间模拟的,题目的范围是【1,3000】,我的 for 循环是 1-3000,突然想到有些任务可能到 3000 的时候一直没有程序员空闲,所以 for 循环至少要到 6000 才行,这样才能 ac 吧。
感觉模拟到 6000 也不行。应该是任务队列判空为止才行。
- #include<bits/stdc++.h>
- #define pb push_back
- typedef long long ll;
- using namespace std;
- typedef pair<int, int> pii;
- const int maxn = 3e3 + 10;
- struct node {
- int id, p, s, pr, t;
- };
- int n, m, p;
- node a[maxn];
- //这里扩大范围
- int f[maxn * 2];
- int res[maxn];
- class cmp {
- public:
- bool operator()(const node&x, const node&y) {
- if(x.pr == y.pr) {
- if(x.t == y.t) {
- return x.s < y.s;
- } else {
- return x.t < y.t;
- }
- } else {
- return x.pr > y.pr;
- }
- }
- };
- set<node, cmp> data[maxn];
- void solve() {
- int x, y, x1, y1;
- scanf("%d%d%d", &n, &m, &p);
- for (int i = 1; i <= p; i++) {
- scanf("%d%d%d%d", &x, &y, &x1, &y1);
- a[i] = {i, x, y, x1, y1};
- }
- sort(a + 1, a + p + 1, [](const node&x, const node&y)->bool{return x.s < y.s;});
- int cur = 0;
- f[1] = m;
- set<int> se;
- x = 1;
- int cnt = 0;
- //这里应该模拟到6000, 保证所有的任务都有机会执行,或者更大。
- for (int i = 1; i <= 3000; i++) {
- cur += f[i];
- while(x <= p) {
- //cout << x << endl;
- if(a[x].s == i) {
- data[a[x].p ].insert(a[x]);
- //cout << "asd " << a[x].id << endl;
- x++;
- cnt++;
- } else break;
- }
- if(cur <= 0 || cnt == 0) continue;
- int t = cur;
- for (int j = 0; j < t; j++) {
- int id = -1;
- int ti = 0;
- for (int k = 1; k <= n; k++) {
- if(data[k].size() == 0)
- continue;
- else {
- // cout << k << " asd " << (data[k].begin())->t << endl;
- if(id == -1 || (data[k].begin())->t < ti) {
- id = k;
- ti = (data[k].begin())->t;
- }}
- }
- //cout << id << " " << ti << endl;
- cur--;
- cnt--;
- node nd = *data[id].begin();
- data[id].erase(data[id].begin());
- res[nd.id] = i + nd.t;
- f[i + nd.t]++;
- if(cnt <= 0 || cur <= 0) break;
- }
- }
- for (int i = 1; i <= p; i++)
- printf("%d\n", res[i]);
- }
- int main() {
- freopen("test.in", "r", stdin);
- //freopen("test.out", "w", stdout);
- solve();
- return 0;
- }
8.22 今日头条笔试
来源: http://www.bubuko.com/infodetail-2275524.html