忍者ブログ
29 March

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

02 January

POH! Vol.1

paizaオンラインハッカソン Vol.1

問題文

https://paiza.jp/poh/ec-campaign



解法

全商品に対して、キャンペーン設定金額の内で最大になる対応を二分探索で探し、
その組み合わせの中でさらに最大値をとる。
最大ケースだとTLEになるかなと思ったけど、
大丈夫だったらしい。



#include<iostream>
#include<vector>
#include<functional>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstdlib>

using namespace std;

int binary_s(vector<int> v,int target);

int main(void){
    int N,D;
    vector<int> item;    //商品の値段
    vector<int> goal;    //キャンペーン設定金額
    scanf("%d%d\n",&N,&D);
    for(int i=0;i<N;i++){
        int a;
        scanf("%d\n",&a);
        item.push_back(a);
    }
    for(int i=0;i<D;i++){
        int a;
        scanf("%d\n",&a);
        goal.push_back(a);
    }
    //ここまで読み込み

    sort(item.begin(),item.end());//商品の値段順ソート
    
    for(int i=0;i<D;i++){    //キャンペーン設定金額ループ
        int ans = 0;
        
        if(item[0]+item[1]>goal[i])cout << 0 << endl;    //最低の商品2つの合計の値段が設定金額を超えていたら0
        else{
        //item[]:商品金額 goal[i]:キャンペーン設定金額 ans:最小値格納用

            for(int j=0;j<N;j++){
                if(item[j]>=goal[i])continue;
                int a = binary_s(item,goal[i]-item[j]);
                if(item[a] + item[j] == goal[i] && a!=j){
                    ans=item[a] + item[j];
                    break;
                }
                if(a==j)a-=1;
                if(item[a] + item[j]>goal[i])continue;
                ans = std::max(ans,item[j] + item[a]);            
            }
            cout << ans << endl;
        }
    }
    
    return 0;
}



int binary_s(vector<int> v,int target){
    int Mid=v.size()/2,Max=v.size()-1,Min=0;
    int PreMid = 0;
    while(Mid!=PreMid){
        PreMid = Mid;
        if(v[Mid] == target)return Mid;
        else if(v[Mid]>target){
            Max=Mid;
            Mid=(Max+Min)/2;
        }else{
            Min=Mid;
            Mid=(Max+Min)/2;
        }
    }
    
    if(target<v[Mid])return Mid-1;
    else return Mid;
}

PR