poj2010 Moo University - Financial Aid

제목: 모두 C 명의 송아지 가 있 습 니 다. 학교 에서 N 명의 소 를 모집 하여 입학 하려 고 합 니 다. 모두 F 장학금 을 제공 할 계획 입 니 다. 송아지 한 명당 두 가지 속성, 성적 과 희망 장학금 이 있 습 니 다. 모집 한 N 명의 송아지 중 가장 큰 숫자 는?사고: 먼저 C 명의 소 를 성적 에 따라 순 위 를 매 긴 다음 에 모든 송아지 의 성적 을 중위 로 하 는 상황 이 문제 의 뜻 을 만족 시 키 는 지 매 거 한다.low [i], up [i] 배열 에 따 르 면 i 를 중위 로 하 는 송아지 앞 장학금 은 최소 합 계 를 요구 하고 i 뒤에 장학금 을 요구 하 는 수량 은 최소 합 계 를 요구한다.통계 과정 은 우선 대기 열 을 빌려 최대 로 쌓 인 다.이 문 제 는 아버지 점 이 있 습 니 다. 제목 의 F 범 위 는 10 억 입 니 다. 처음에 저 는 최대 경계 inf = 0x7ffffff f (20 억 여 만) 를 설 치 했 습 니 다. 뒤에 산술 조작 이 있 는데 바로 넘 쳤 습 니 다. 나중에 0x7ffff (1 억 여 만) 로 바 뀌 었 고 Wa 로 바 뀌 었 습 니 다. 오랫동안 잘못 을 찾 았 는데 여기 라 는 것 을 알 게 되 었 습 니 다.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<limits>
#include<algorithm>
using namespace std;
const int maxn=100000+10,inf=10*0x7ffffff;
pair<int,int>cow[maxn];
int low[maxn],up[maxn];

int main()
{
   int n,c,f;
   //cout<<inf<<" "<<10*0x7ffffff<<endl;
   while(~scanf("%d%d%d",&n,&c,&f)){
     int half=n/2;
     for(int i=0;i<c;i++){
        scanf("%d%d",&cow[i].first,&cow[i].second);
     }
     sort(cow,cow+c);
     priority_queue<int>pque;
     int total=0;
     for(int i=0;i<c;i++){
        low[i]=pque.size()==half ? total : inf;
        total+=cow[i].second;
        pque.push(cow[i].second);
        while(pque.size()>half){
            int temp=pque.top();
            total-=temp;
            pque.pop();
        }
     }
     while(!pque.empty()) pque.pop();
     total=0;
     for(int i=c-1;i>=0;i--){
        up[i]=pque.size()==half ? total : inf;
        total+=cow[i].second;
        pque.push(cow[i].second);
        while(pque.size()>half){
            int temp=pque.top();
            total-=temp;
            pque.pop();
        }
     }
     int ans=-1;
     for(int i=c-1;i>=0;i--){
        if(low[i]+cow[i].second+up[i]<=f){
            ans=cow[i].first;
            break;
        }
     }
     printf("%d
",ans);
   }
}
Cocos2d-x 3.1 Lua Binding
IOS - --- Controller 다이어트 1: UITableView 를 벗 기 고 dataSource 와 deleagte 를 패키지 합 니 다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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