XSY3244 10.31 D

제목:

수축에\(N\)마리 쥐\(M\)구멍이 있고 구멍마다 용량이 있어 모든 쥐가 구멍에 들어가는 최소한의 대가를 요구한다.(\(N, M\leq1000000\), 시한\(2s\)

문제 풀이:

대감의 앞의 두 문제에 걸려서 취생몽사해서 경기장에서 이 문제를 전혀 보지 못했다...
10만 개의 파일은 분명히\(dp\) 할 수 있고, 라인 트리 같은 것을 추가하면 된다.
100%의 데이터에 대해 위의 그\(dp\)는 이미 쓸모가 없다. 대리인이 준 방법은 욕심을 정반하고 쥐 한 마리가 욕심을 내서 왼쪽/오른쪽의 가장 가까운 구멍을 선택하도록 하는 것이다.쥐 한 마리에 대해 이 두 구멍은 바로 그것이 최종 결정을 내릴 구멍이다.그리고 쥐를 쥐가 들어갈 수 있는 구멍과 함께 몇 축 위에 놓고\(dp\)를 한 번 하세요.상태\(f {i, j}\)는 제\(i\)개 점을 얻었음을 나타낸다. 쥐는 구멍보다\(j\)개 많아서 옮기기가 매우 간단하다.이것\(dp\)은 위의 그것과 비교하면 바늘로 점프\(O(1)\)를 직접 이동할 수 있다는 장점이 있다.시공의 복잡도는 모두 선형이다.
경기장에서 또 다른 방법을 생각해 낸 사람이 있다.이것은 내 코드의 방법이다.
우리는 모형을 하나 세웠다.

쥐와 구멍에 대해 우리는 각각 두 개의 큰 뿌리 더미\(M, H\)로 저장하고 위치에 따라 저장한다.

쥐와 구멍을 위치에 따라 정렬한다.

현재 처리된 쥐가 있다면\(H\) 더미의 꼭대기를 취하여 이 구멍에 넣고 이 용량\(-1\)을 흠정하고 쥐를 거울로 삼아 이 구멍이 반사된 곳에\(M\) 더미에 쥐 한 마리를 삽입하여 답을 갱신한다.

현재 처리된 구멍이 있다면\(M\) 무더기의 모든 좌표가 그것보다 큰 쥐를 이 구멍으로 굴러 들어가게 한다(분명히 쥐보다 현재 구멍 안에 있는 것이 더 좋다). 그러나 이것이 가장 좋은 것은 아니다. 그래서 우리는 후회 메커니즘을 세워야 한다.\(\Delta=현재 구멍의 좌표-이 쥐의 좌표\)\(현재 구멍 좌표 현재 구멍 좌표 +\Delta\)의 새로운 용량이 하나의 구멍이다.답안을 업데이트하고 모든 것을 처리한 후에 현재 구멍에 남은 용량이 있다면 그것을 더미에 던져라.왜 그런지 생각해 봐.코드:

#include
#include
#include
#include
#include
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define of(i,l,r) for(int i=l;i>=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
using namespace std;
typedef long long ll;
typedef pair pli;
#define P(a,b) make_pair(a,b)
inline void open(const char *s)
{
  #ifndef ONLINE_JUDGE
  char str[20];
  sprintf(str,"in%s.txt",s);
  freopen(str,"r",stdin);
//    sprintf(str,"out%s.txt",s);
//    freopen(str,"w",stdout);
  #endif
}
inline ll rd()
{
  static ll x,f;
  x=0;f=1;
  char ch=getchar();
  for(;ch'9';ch=getchar())if(ch=='-')f=-1ll;
  for(;ch>='0'&&ch<='9';ch=getchar())x=x*10ll+ch-'0';
  return f>0?x:-x;
}
const int N=1000010;
int n,m;
ll ans=0;
pli a[N<<1];
priority_queueM;
priority_queueH;

inline void gaoM(pli x)
{
  ll res=1000000000000000ll;
  if(!H.empty()){
      pli y=H.top();H.pop();
      res=x.first-y.first;
      if(--y.second)H.push(y);
  }
  M.push(x.first+res);
  ans+=res;
}
inline void gaoH(pli x)
{
  while(x.second&&!M.empty()&&M.top()>x.first){
      ll y=M.top();M.pop();
      ll res=x.first-y;x.second--;
      ans+=res;H.push(P(x.first+res,1));
  }
  if(x.second)H.push(x);
}

int main()
{
  open("c");
  n=rd();m=rd();
  fo(i,1,n)a[i].first=rd(),a[i].second=-1;
  ll s=0;
  fo(i,1,m)a[n+i].first=rd(),a[n+i].second=rd(),s+=a[n+i].second;
  if(s

전재 대상:https://www.cnblogs.com/JackyhhJuRuo/p/9884190.html

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

XSY3244 10.31 D

XSY3244 10.31 D

제목:

문제 풀이:

좋은 웹페이지 즐겨찾기