AcWing 467. 海港    原题链接    中等

作者： 作者的头像   Hicode002 ,  2019-12-14 14:30:53 ,  所有人可见 ,  阅读 1476

1


3

算法1

(暴力枚举) $O(nk)$

这道题很坑，40分很好做，只要桶排一遍即可，70分只要桶排前挑出符合时间的即可，100分用到stl了，用queue存每个人的时间与国籍，每次找不符合时间的，把它出队，桶内–；
注意：
1.struct存时间和国籍
2.统计的是不符合时间的而不是符合时间的
3.每次以前一次的统计为基础，减去不符合时间的不同国籍数就是这次的不同总人数
4.queue要记得判断是否empty（），不直接调用front（），这样会re，当queue 空时，只需统计这次国籍不同数量即可，不用找之前的。

参考文献

C++ 代码

#include<iostream>//can`t
#include<cstdio>//can`t
#include<cstring>//can`t
#include<string>//can`t
#include<cmath>
#include<fstream>
#include<sstream>
#include<ctime>//can`t
#include<cstdlib>//can`t
#include<cfloat>//can`t
#include<climits>//can`t
#include<iomanip>
#include<stack>//can`t
#include<queue>//can`t
#include<deque>//can`t
#include<map>//can`t
#include<set>//can`t
#include<bitset>//can`t
#include<vector>//can`t
#include<algorithm>//can`t
#define ll long long
#define ui unsigned
#define re register
#define fop(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define fc() fclose(stdin),fclose(stdout)

using namespace std;//can`t

inline void myread(int&x){
    char a,f=1;
    x=0;
    a=getchar();
    if(a>='0'&&a<='9')x=a-48;
    else if(a=='-')f=-1;
    while(1){
        a=getchar();
        if(a>='0'&&a<='9')x=x*10+a-48;
        else {x=x*f;return;
        }
    }
}
inline void mywrite(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)mywrite(x/10);
    putchar(x%10+48);
}
struct people{
    int time,ji;
};
queue<people>port;
int gjs[100007];
void tests(const int& totp){
    cout<<'\n';
    for(re int i=0;i<100007;++i){

        if(gjs[i]!=0)cout<<"test:"<<i<<" geshu:"<<gjs[i]<<' ';
    }
    cout<<endl<<"totp:"<<totp<<"\n";
}
int main(){
    memset(gjs,0,sizeof(gjs));
    int n,totp=0;
    myread(n);
    for(re int i=0;i<n;++i){
        int t,k;
        myread(t),myread(k);
        if(!port.empty() ){

            while(1){
                if(port.empty() ||port.front() .time>t-86400)break;

                else{

                    --gjs[port.front() .ji];
                    if(gjs[port.front() .ji]==0)--totp;
                    port.pop() ;

                }
            }
        }
        for(re int j=0;j<k;++j){
            int x;
            myread(x);
            people lin;
            lin.ji =x;
            lin.time =t;
            port.push(lin);
            if(gjs[x]==0)++totp;
            ++gjs[x];
        //  tests(totp);
        }
        mywrite(totp),putchar('\n');
    }
    return 0;
}

3 评论

用户头像
哈哈哈hh   2020-06-16 13:11         踩      回复

我这里怎么错了，求指点，

#include <iostream>
using namespace std;
#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
const int N = 100001;


int main()
{
    int n = 0;
    int t = 0;
    int k = 0;
    set<int> s;
    int sum = 0;
    cin >> n;

    pair<int, vector<int>> a[N]; // t时间的数组
    int r = 0;
    int l = 0;
    map<int, int> mymap;
    for (int i = 0; i < n; i++)
    {
        cin >> t;
        cin >> k;
        vector<int> c(k);
        for (int i = 0; i < k; i++)
        {
            cin >> c[i];
            mymap[c[i]]++;
        }
        a[r++] = make_pair(t, c);
        while (l < r &&  t - a[l].first > 86400)
        {
            for (int j = 0; j < a[l].second.size(); j++)
            {
                mymap[a[l].second[j]]--;
                if (mymap[a[l].second[j]] == 0)
                {
                    mymap.erase(a[l].second[j]);
                }
            }
            l++;
        }
        sum = mymap.size();


        printf("%d\n", sum);
    }
}
用户头像
Hicode002   2020-08-24 17:37         踩      回复

解决了吗？

用户头像
qiaoxinwei   2020-09-15 09:44         踩      回复
  • t - a[l].first > 86400应该是t - a[l].first > =86400，这样就可以过17个样例了，^_^。
  • 这里使用vector不太合适，$t_i$是递增的，可以使用队列的滑动窗口实现，详细的可以看我的题解。