세계 아이스하키 선수권대회 문제 풀이.

세계 아이스하키 선수권대회 문제 풀이.
반절 하여 누 드 문 제 를 검색 하 다.
우 리 는 먼저 앞의 절반 의 모든 방안 을 매 거 할 수 있 습 니 다. 모두 \ (2 ^ {20} = 1048576 \ \ approx 1000000 \) 종류 가 있 습 니 다.
(배열 의 크기 가 1048576 보다 크 고 작가 가 처음 제출 한 것 은 1000000 만 개 밖 에 안 되 었 습 니 다. 솥 이 열 렸 습 니 다)
하나의 배열 c 로 저장 하고 정렬 합 니 다.
매 거 진 후반 의 방안 에 그 비용 을 w 로 설정 하 다.
w 에 따라 큰 것 부터 작은 것 까지 정렬 합 니 다.
단조 로 운 포인터 로 c 배열 의 m - w 이하 프로젝트 개 수 를 유지 합 니 다.
ans 누적 방안 개수.
(w 큰 것 부터 작은 것 까지 m - w 작은 것 부터 큰 것 까지 지침 이 단 조 롭 고 오른쪽으로 이동)
물론 당신 도 분 산 된 후에 접두사 와 (너무 귀 찮 고 쓰 지 않 음) 를 사용 할 수 있 습 니 다.
정렬 후 upper bound (쓸데없는 짓)
코드:
#include
#define ll long long
using namespace std;
const int N=2e6+6;
int l=1,n1,n2,n,num1=0,num2=0;
ll t,m,ans=0,a[N],b[N],c[N],d[N];
inline ll read(){
   ll T=0,F=1; char ch=getchar();
   while(ch'9'){if(ch=='-') F=-1; ch=getchar();}
   while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
   return F*T;
}
void dfs(int x,ll y,int z,ll p[],ll q[],int &num){
     if(y>m) return;
     if(x>z){p[++num]=y; return;}
     dfs(x+1,y,z,p,q,num),dfs(x+1,y+q[x],z,p,q,num);
}
int main(){
    n=read(),m=read(),n1=(n>>1),n2=n-n1;
    for(int i=1;i<=n1;++i) a[i]=read();
    for(int i=1;i<=n2;++i) b[i]=read();
    dfs(1,0,n1,c,a,num1),sort(c+1,c+num1+1);
    dfs(1,0,n2,d,b,num2),sort(d+1,d+num2+1);
    for(int i=num2;i>=1;--i){
        t=m-d[i];
        while(l<=num1&&c[l]<=t) ++l;
        ans+=1ll*(l-1);
    } 
    printf("%lld
",ans);
    return 0;
}

다음으로 전송:https://www.cnblogs.com/ljk123-de-bo-ke/p/11323178.html
자바 응용 프로그램 은 Liux 에 원 격 으로 로그 인하 여 명령 을 수행 합 니 다.
Java foreach 원리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage