Wunder 펀드 라운드 2016 F. 더 블 스냅 백 (두 포인터 + 비둘기 우리 원리)
N ≤ 106 요소 의 multiset 2 개 를 정 하고 요소 의 수치 범 위 는 1 ∼ N 입 니 다. 현재 각각 그 중에서 일부 요 소 를 선택 한 subset 이 고 subset 도 multiset 입 니 다. 그들의 합 이 같 고 출력 각자 의 크기 와 하 표 가 있 으 며 해 출력 이 없습니다 - 1
분석:
분명히 O (n) 의 알고리즘 이 필요 합 니 다. 2 개의 시퀀스 에 따라 prefix 가 필요 합 니 다. sum 은 점차 증가 합 니 다. 우 리 는 two 를 사용 할 수 있 습 니 다. pointers 는 suman ≤ sumbn 을 가정 하고 모든 sumai 에 대해 우 리 는 two 를 사용한다. pointers 는 가장 큰 j 를 찾 아 sumai ≥ sumbj 로 하여 금 dif = sumai - sumbj 를 얻 게 했다. dif 는 분명히 8712 ° 0, n - 1] 이다. 이런 차 이 는 n 개 이 고 공 집 된 suma 0 - sumb 0 = 0 을 더 하면 (n + 1) 개가 비둘기 우리 원리 에 따라 반드시 2 개의 차이 가 있 을 것 이다. 그러면 우 리 는 구조 해 를 얻 었 다.
코드:
//
// Created by TaoSama on 2016-01-31
// Copyright (c) 2015 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
typedef long long LL;
int n, a[N], b[N];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d", &n) == 1) {
LL s1 = 0, s2 = 0;
for(int i = 1; i <= n; ++i) scanf("%d", a + i), s1 += a[i];
for(int i = 1; i <= n; ++i) scanf("%d", b + i), s2 += b[i];
bool flipped = false;
if(s1 > s2) swap(a, b), flipped = true;
vector<pair<int, int> > pos(n);
for(auto &x : pos) x = { -1, -1};
pos[0] = {1, 1};
vector<int> ans1, ans2;
LL xs = 0, ys = 0;
for(int i = 1, j = 1; i <= n;) {
xs += a[i++];
while(j <= n && ys + b[j] <= xs) ys += b[j++];
int dif = xs - ys;
if(~pos[dif].first) {
for(int k = pos[dif].first; k < i; ++k) ans1.push_back(k);
for(int k = pos[dif].second; k < j; ++k) ans2.push_back(k);
break;
}
pos[dif] = {i, j};
}
if(flipped) swap(ans1, ans2);
printf("%d
", ans1.size());
for(int i = 0; i < ans1.size(); ++i)
printf("%d%c", ans1[i], "
"[i == ans1.size() - 1]);
printf("%d
", ans2.size());
for(int i = 0; i < ans2.size(); ++i)
printf("%d%c", ans2[i], "
"[i == ans2.size() - 1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2020 우 객 여름 다 교 훈련소 (6 차 전) K - Bag [슬라이딩 창]제목 링크:https://ac.nowcoder.com/acm/contest/5671/K 제목 k - bag 를 1 ~ k 로 정의 하 는 여러 개의 전체 배열 로 구 성 된 서열, part - k - bag 는 k ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.