[luoguP2672] 판매원(욕심+트리 배열+우선 대기열)
욕심고구마 증명은 할 수 없다...
매번 가장 큰 것을 찾으면 됩니다. 가장 큰 것을 찾으면 수열은 좌우 양쪽으로 나뉘고 왼쪽은 stl 우선 대기열로 유지하고 오른쪽은 나무 모양의 그룹으로 유지합니다.
(세그먼트 트리 시간 초과...)
코드 #include
#include
#include
#define N 100001
#define ls now << 1
#define rs now << 1 | 1
#define max(x, y) (p[x].a * 2 + p[x].b > p[y].a * 2 + p[y].b ? (x) : (y))
int n, last, now, ans, M[N];
std::priority_queue q;
struct node
{
int a, b;
}p[N];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}
inline void add(int x, int d)
{
for(; x; x -= x & -x) M[x] = max(M[x], d);
}
inline int query(int x)
{
int ret = 0;
for(; x <= n; x += x & -x) ret = max(ret, M[x]);
return ret;
}
int main()
{
int i, j, x;
n = read();
for(i = 1; i <= n; i++) p[i].a = read();
for(i = 1; i <= n; i++) p[i].b = read();
for(i = 1; i <= n; i++) add(i, i);
last = 0;
for(i = 1; i <= n; i++)
{
now = query(last + 1);
if(q.empty() || (q.top() < (p[now].a - p[last].a) * 2 + p[now].b))
{
for(j = last + 1; j < now; j++) q.push(p[j].b);
ans += (p[now].a - p[last].a) * 2 + p[now].b;
last = now;
}
else
{
ans += q.top();
q.pop();
}
printf("%d
", ans);
}
return 0;
}
전재 대상:https://www.cnblogs.com/zhenghaotian/p/7087246.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
#include
#include
#define N 100001
#define ls now << 1
#define rs now << 1 | 1
#define max(x, y) (p[x].a * 2 + p[x].b > p[y].a * 2 + p[y].b ? (x) : (y))
int n, last, now, ans, M[N];
std::priority_queue q;
struct node
{
int a, b;
}p[N];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}
inline void add(int x, int d)
{
for(; x; x -= x & -x) M[x] = max(M[x], d);
}
inline int query(int x)
{
int ret = 0;
for(; x <= n; x += x & -x) ret = max(ret, M[x]);
return ret;
}
int main()
{
int i, j, x;
n = read();
for(i = 1; i <= n; i++) p[i].a = read();
for(i = 1; i <= n; i++) p[i].b = read();
for(i = 1; i <= n; i++) add(i, i);
last = 0;
for(i = 1; i <= n; i++)
{
now = query(last + 1);
if(q.empty() || (q.top() < (p[now].a - p[last].a) * 2 + p[now].b))
{
for(j = last + 1; j < now; j++) q.push(p[j].b);
ans += (p[now].a - p[last].a) * 2 + p[now].b;
last = now;
}
else
{
ans += q.top();
q.pop();
}
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
