#32917: 想法+詳解


jasperlin0108@gmail.com (Jasper Lin)

School : 高雄市立高雄高級中學
ID : 169403
IP address : [114.40.142.198]
Last Login :
2023-10-05 16:52:06
f581. 3. 圓環出口 -- 2020年7月APCS | From: [220.142.163.15] | Post Date : 2022-11-17 00:08

想法:前綴和+二分搜

        因為題目要求走房間拿分數,而且房間又是連續的,所以可以想到區段求和=====>前綴和

        又因為前綴和是由小到大=====>二分搜

        附上程式碼(英文不好,變數名稱可能有點詭異)

 

 

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n,m;
    vector<long long> point;
    vector<long long> addpoint;
    vector<long long> task;
    stringstream ss;
    string s;
    cin>>n>>m;
    cin.ignore();
    getline(cin,s);
    ss<<s;
    int si=0;
    while(getline(ss,s,' ')){
        point.push_back(atoi(s.c_str()));
        if(si==0){
            addpoint.push_back(point[si]);
        }
        else{
            addpoint.push_back(addpoint[si-1]+point[si]);
        }
        si++;
    }
    ss.str("");
    ss.clear();
    getline(cin,s);
    ss<<s;
    while(getline(ss,s,' ')){
        task.push_back(atoi(s.c_str()));
    }
    int room=0;
    long long sum=addpoint[n-1];
    for(int i=0;i<task.size();i++){
        if(room!=0){
            task[i]+=addpoint[room-1];
        }
        if(task[i]%sum==0){
            task[i]=sum;
        }
        else{
            task[i]=task[i]%sum;
        }
        auto it=lower_bound(addpoint.begin(),addpoint.end(),task[i]);
        room=(it-addpoint.begin()+1)%n;
    }
    cout<<room;
    return 0;
}

 
ZeroJudge Forum