题解

14 条题解

  • 1
    @ 2016-05-01 00:10:52

    题目分析
      对于第i位选手来说,如果想要夺冠,最好的情况一定是他在下一场夺冠,且其余人按照原有排名的逆序从依次为第二名到第n名。如果先对所有人排序,这样做的时间复杂度是O(n^2)的,可以得到60分。
      再考虑上述过程,可以发现对于从小到大排序后第i位选手和第i+1位选手来说,最优方案下其余人下一场的得分都是一样的,所以只需要顺序处理好两邻选手的情况即可。

  • 0
    @ 2016-10-20 08:20:31

    //小雪非常关注自行车比赛,尤其是环滨湖自行车赛。一年一度的环滨湖自行车赛,需要选手们连续比赛数日,最终按照累计得分决出冠军。
    //今年一共有N位参赛选手。每一天的比赛总会决出当日的排名,第一名的选手会获得N点得分,第二名会获得N-1点得分,第三名会获得N-2点得分,依次类推,最后一名会获得1点得分。保证没有选手会排名相同。
    //在之前的数日较量中,N位选手已经分别累计了一些分数。现在即将开始的是最后一天的比赛。小雪希望知道有多少位选手还有可能获得最终的冠军,也就是说还有多少选手有可能通过最后一天的比赛获得累计总分第一名。
    //第一行输入一个整数N,表示参赛选手总数,保证3<=N<=300000。
    //之后N行,其中第i行输入一个整数B[i]表示第i位选手已经获得的累计分数,满足0<=B[i]<=2000000。
    //输出只有一行,只输出一个整数,表示有多少位选手有可能获得最终的冠军。
    include <cstdio> include <iostream> include <cmath>
    using namespace std;
    int n , k , kl;
    int forn , forBs , forBss , forBss2 , forBssk , maxs , cu , co;
    int B[300001] , Bs[2000001] , Bss[2000001] , Bssmin[2000001];
    void prep()
    {
    //在这道题中,我们引入变量Bssmin:“最大的威胁度”。
    //我们假设要求的人在最后一场比赛中是冠军,而其他的人则是分数越高、最后一次比赛名次越低。
    //那么,每一个总分高于他的人,都会对他的冠军造成“威胁”。
    //威胁度=分数+在此分数及之前一共有多少人。
    //显然,一旦某个人的威胁度超过了他的分数,他就绝无可能获得冠军了。

    scanf("%d",&n);
    for (forn=1;forn<=n;forn++)
    {
    scanf("%d",&B[forn]);
    if (maxs < B[forn]) maxs = B[forn];//取最大值
    }

    for (forn=1;forn<=n;forn++)
    if (maxs < B[forn]+n) Bs[B[forn]]++;//通过最大值,初步判断有哪些选手可以超越冠军,并把当前的分数出现次数记录下来

    for (forBs=maxs;forBs>=1;forBs--)
    if (Bs[forBs] > 0) Bss[++forBssk] = forBs;//然后,将所有出现过的分数记录下来

    for (forBss=2;forBss<=forBssk;forBss++)//冠军没有威胁,因此我们从2开始
    {
    k = k + Bs[Bss[forBss-1]];//统计 在此分数及之前一共有多少人
    if (Bss[forBss-1] + k > kl)//在一定的分数之后,同一个分数对所有剩下的选手的威胁都是最大的,因此我们需要找出它
    {
    kl = Bss[forBss-1] + k;
    Bssmin[forBss] = kl;//确定一个分数段收到的最大威胁
    }
    }
    return;
    }
    void sear()
    {
    for (forBss=1;forBss<=forBssk;forBss++)
    if(Bss[forBss] + n > Bssmin[forBss]) co = co + Bs[Bss[forBss]];
    printf("%d",co);
    return;
    }
    int main()
    {
    prep();
    sear();
    return 0;
    }
    //英国
    //国际上造成最大威胁的国家是 芬兰。
    //他们对我们的威胁是226.1。
    //—————————————————————
    //你可能并没有被这个国家威胁。
    //他们的好战度可以合理化你的侵略行为。(笑)

    • @ 2016-10-20 08:22:32

      顺便,这个方法需要极长的代码,理解起来也比较困难,但运行速度会很快

  • 0
    @ 2016-10-19 17:01:52

    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    int cmp(const int &a,const int &b)
    {
    if (a<b) return 1;
    else return 0;
    }
    int main()
    {
    int n;
    int d[6000000];
    int a[6000000];
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    scanf("%d",&d[i]);
    sort(d+1,d+n+1,cmp);
    int tot=0;

    for (int i=n;i>=1;i--)
    {
    a[i]=0;
    if (a[i+1]==0 && i!=n) goto loop;
    a[i]=1;
    for (int j=n;j>=i;j--)
    if (d[j]-j+1>d[i]) {
    a[i]=0;break;}
    loop:tot=tot+a[i];
    }
    printf("%d",tot);
    return 0;
    }

  • 0
    @ 2016-10-18 16:56:40

    这也能过。。。
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=300010;
    int a[maxn],n,mx=0,ans=0;
    int main()
    {
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",a+i);
    sort(a,a+n);
    for(int i=n-1;i>=0;--i) if(a[i]+n-i>mx) mx=a[i]+n-i;
    for(int i=0;i<n;++i) if(a[i]+n>=mx) ++ans;
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2016-10-18 16:55:01

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;

    const int maxn=300010;

    int a[maxn],n,mx=0,ans=0;

    int main()
    {
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",a+i);
    sort(a,a+n);
    for(int i=n-1;i>=0;--i) if(a[i]+n-i>mx) mx=a[i]+n-i;
    for(int i=0;i<n;++i) if(a[i]+n>=mx) ++ans;
    cout<<ans;

    return 0;
    }

  • 0
    @ 2016-09-18 16:44:51
    评测结果
    编译成功
    
    测试数据 #0: Accepted, time = 0 ms, mem = 4420 KiB, score = 5
    测试数据 #1: Accepted, time = 0 ms, mem = 4420 KiB, score = 5
    测试数据 #2: Accepted, time = 0 ms, mem = 4424 KiB, score = 5
    测试数据 #3: Accepted, time = 0 ms, mem = 4420 KiB, score = 5
    测试数据 #4: Accepted, time = 0 ms, mem = 4420 KiB, score = 5
    测试数据 #5: Accepted, time = 0 ms, mem = 4424 KiB, score = 5
    测试数据 #6: Accepted, time = 0 ms, mem = 4424 KiB, score = 5
    测试数据 #7: Accepted, time = 0 ms, mem = 4424 KiB, score = 5
    测试数据 #8: Accepted, time = 15 ms, mem = 4424 KiB, score = 5
    测试数据 #9: Accepted, time = 0 ms, mem = 4424 KiB, score = 5
    测试数据 #10: Accepted, time = 31 ms, mem = 4424 KiB, score = 5
    测试数据 #11: Accepted, time = 31 ms, mem = 4420 KiB, score = 5
    测试数据 #12: Accepted, time = 31 ms, mem = 4424 KiB, score = 5
    测试数据 #13: Accepted, time = 46 ms, mem = 4424 KiB, score = 5
    测试数据 #14: Accepted, time = 31 ms, mem = 4424 KiB, score = 5
    测试数据 #15: Accepted, time = 46 ms, mem = 4424 KiB, score = 5
    测试数据 #16: Accepted, time = 15 ms, mem = 4420 KiB, score = 5
    测试数据 #17: Accepted, time = 46 ms, mem = 4424 KiB, score = 5
    测试数据 #18: Accepted, time = 46 ms, mem = 4420 KiB, score = 5
    测试数据 #19: Accepted, time = 62 ms, mem = 4420 KiB, score = 5
    Accepted, time = 400 ms, mem = 4424 KiB, score = 100
    代码
    #include <algorithm>
    #include <cstdio>
    using std :: sort;
    int n,a[1000001];
    inline int read() {
      int p = 1,x;
      char c;
      while ((c = getchar()) < '0' || c > '9') if (c == '-') p = -1;
      x = c-'0';
      while ((c = getchar()) >= '0' && c <= '9') x = x*10+c-'0';
      return x*p;
    }
    inline void write(int x) {
      int t[20];
      t[0] = 0;
      if (x < 0) putchar('-'),x = -x;
      while (x) t[++t[0]] = x%10,x /= 10;
      for (int i = t[0];i >= 1;i--) putchar(t[i]+'0');
    }
    int main() {
      n = read();
      for(int i = 1;i <= n;i++) a[i] = read();
      sort(a+1,a+n+1);
      int ans = 1;
      for(int i = 1;i < n;i++)
      if(a[i]+n >= a[n]+1) ans++;
      write(ans);
      return 0;
    }
    
  • 0
    @ 2016-08-30 13:07:48

    var
    i,n,m,j:longint;
    a:array[1..1000000]of longint;

    procedure qs(l,r:longint);
    var
    i,j,mid,p:longint;
    begin
    i:=l;j:=r;
    mid:=a[(i+j) div 2];
    repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
    begin
    p:=a[i];a[i]:=a[j];a[j]:=p;
    inc(i);dec(j);
    end;
    until i>j;
    if l<j then qs(l,j);
    if i<r then qs(i,r);
    end;

    begin
    readln(n);m:=0;
    for i:=1 to n do
    readln(a[i]);
    qs(1,n);
    for i:=n downto 1 do
    if a[i]+n-i+1>m then m:=a[i]+n-i+1;
    j:=0;
    for i:=1 to n do
    if a[i]+n>=m then inc(j);
    writeln(j);readln;readln;
    end.
    学了不久
    不小心加了两个readln,结果tle了

  • 0
    @ 2016-08-11 16:08:21

    一开始傻逼了。。。
    不知道为什么
    也不知道我的程序到底干了什么
    就来回地加接着比较
    然后就。。。AC了。。。
    我也是醉了!

  • 0
    @ 2016-07-14 15:29:44

    很简单,重庆的智障来打架了,

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n;
    int num[1000010];
    int main()
    {
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++)
    scanf("%d",&num[i]);
    sort(num+1,num+n+1);
    int ans = 1;
    for(int i = 1 ; i < n ; i ++)
    if(num[i] + n >= num[n] + 1)
    ans ++;
    printf("%d\n",ans);
    return 0;
    }

    • @ 2016-09-06 14:59:09

      卧槽这样不是连样例都过不了?数据太弱了吧?

  • 0
    @ 2016-07-04 11:28:44

    C:
    int n;
    int num[1000010];
    #include <stdio.h>
    // 快排
    void Qu(int arr[], int L, int R) {
    int i = L;
    int j = R;
    int v = arr[(i+j)/2];
    while(i <= j) {
    while(arr[i] < v) {
    i++;
    }
    while(arr[j] > v) {
    j--;
    }
    if(i <= j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    i++;
    j--;
    }
    }
    if(L < j) {
    Qu(arr, L, j);
    }
    if(i < R) {
    Qu(arr, i, R);
    }
    }

    int main()
    {
    scanf("%d",&n);
    int i, count=0, max=-1;
    for(i = 1 ; i <= n ; i ++)
    scanf("%d",&num[i]);
    Qu(num, 1, n);
    for(i = 1 ; i <= n ; i ++) {
    if(max < num[i]) {
    max = num[i];
    count = 0;
    }
    else if(max == num[i]) count++;
    }
    int ans = 1;
    for(i = 1 ; i < n ; i ++)
    if(num[i] + n > num[n] + count)
    ans ++;
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2016-05-06 20:50:20

    Pascal AC
    var a:array[1..300000]of longint;
    i,n,m,s:longint;
    procedure kp(l,r:longint);
    var i,j,m,s:longint;
    begin
    i:=l;
    j:=r;
    m:=a[(i+j)div 2];
    repeat
    while a[i]<m do inc(i);
    while a[j]>m do dec(j);
    if i<=j then
    begin
    s:=a[i];
    a[i]:=a[j];
    a[j]:=s;
    inc(i);
    dec(j);
    end;
    until i>j;
    if i<r then kp(i,r);
    if l<j then kp(l,j);
    end;

    begin
    readln(n);
    for i:=1 to n do readln(a[i]);
    kp(1,n);
    s:=0;
    for i:=n downto 1 do
    if a[i]+n-i+1>s then s:=a[i]+n-i+1;
    m:=0;
    for i:=1 to n do
    if a[i]+n>=s then inc(m);
    write(m);
    end.

  • 0
    @ 2016-05-01 01:02:25

    一种奇怪的做法:

    首先,要使当前排名为i的选手尽量高,其他选手尽量低,那么他最后一场应该获得n分,当前排名1~i-1的选手分别获得1,2,...,i-1分,排名i+1~n的选手分别获得i,i+1,i+2...,n-1分。
    很明显,除去第i位选手来说,给其他选手加上的分数都是递增的。
    所以我们就先依次将分数加上1,2,3......,
    这样我们可以发现,当处理第i名选手时,他的分数是score[i]+n-i,第1名到第i-1名选手中最后得分最高的就是score[1]到score[i-1]的最大值,第i+1名到第n名得分最高就是score[i+1]到score[n]的最大值-1

    所以RMQ即可,O(nlogn)预处理,O(n)求解

    代码实现和描述略有不同……代码中排序是从小到大的,所以后面的判断也略有不同

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <cmath>
    #define INF 100000009
    using namespace std;
    int n,ans=0;
    int sc[300005];
    int dp[300005][20];
    int getlen(int x) {
    int ans=0;
    while (1<<ans <= x) {
    ++ans;
    }
    return ans-1;
    }
    int query(int l,int r) {
    if (r<l)
    return -INF;
    int len=getlen(r-l+1);
    return max(dp[l][len],dp[r-(1<<len)+1][len]);
    }
    int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    scanf("%d",sc+i);
    sort(sc+1,sc+n+1);
    for (int i=1;i<=n;i++) {
    sc[i]+=(n-i);
    dp[i][0]=sc[i];
    }
    for (int k=1,t=2;t <= n;k++,t<<=1) {
    for (int i=1,end=n-t+1;i<=end;i++) {
    dp[i][k]=max(dp[i][k-1],dp[i+(1<<(k-1))][k-1]);
    }
    }
    for (int i=1;i<=n;i++) {
    if (query(1,i-1) <= sc[i]+i && query(i+1,n) <= sc[i]+i-1)
    ans++;
    }
    printf("%d",ans);
    return 0;
    }

  • -1
    @ 2018-08-20 09:12:32
    /*
    不多说我先吐槽一下这个数据有多弱
    我们看下面这个程序
    int n;
    int num[1000010];
    int main()
    {
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++)
    scanf("%d",&num[i]);
    sort(num+1,num+n+1);
    int ans = 1;
    for(int i = 1 ; i < n ; i ++)
    if(num[i] + n >= num[n] + 1)
    ans ++;
    printf("%d\n",ans);
    return 0;
    }
    结果是他AC了
    我心中阴影面积INF?
    我靠这连样例都过不了啊,很明显的一个错误的算法
    根本不可以只判断每个a[i]和a[n]的极值关系
    比如说我们看这组样例
    5
    15
    14
    15
    12
    14
    最小值是是几? 不是5 是4
    因为虽然12+4>15+1
    但是我们可以看到,因为排名是保证没有相同的,所以有两个15
    一个是1,另一个一定最小就是2了
    那么这就非常尴尬了   这数据我给满分啊
    看看标解吧
    对于第i位选手来说,如果想要夺冠,最好的情况一定是他在下一场夺冠,且其余人按照原有排名的逆序从依次为第二名到第n名。
    如果先对所有人排序,这样做的时间复杂度是O(n^2)的,可以得到60分。
    再考虑上述过程,可以发现对于从小到大排序后第i位选手和第i+1位选手来说,最优方案下其余人下一场的得分都是一样的,
    所以只需要顺序处理好两邻选手的情况即可。
    实在有趣
    比赛的时候想到这一步了 但是就差一点点 还是没能AK
    唉真悲伤现在一想很简单啊
    先从小到大排序
    对于每一个a[i](a[n]除外),我们先判断一下他和a[n]的关系咯
    怎么说最优肯定是a[i]第一名a[n]最后一名
    判断是否可行
    然后我们并不需要每个人和除他外所有人比一次
    我们就直接拿这个人和他后面那个人一比就好了
    因为他后面的人一定不可能会追上他
    但是后面那个人就有可能因为加的有点多超过他
    a[i]+n>=a[i+1]+(n-i+1)
    怎么理解呢
    按照标解的意思理解一下就好了
    最好的情况一定是他在下一场夺冠,且其余人按照原有排名的逆序从依次为第二名到第n名
    就是越大排名的越后越好
    所以a[i+1]的名次最好的情况一定是第i+1名
    所以可以得n-i+1分
    然后判断一下就好了
    挺考验逻辑思维的一道题目的
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <iomanip>
    #include <cstdlib>
    using namespace std;
    
    const int maxn=300010;
    int n;
    int ans;
    int a[maxn];
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1);
        for(int i=1;i<=n-1;i++)
            if(a[i]+n>=a[n]+1&&a[i]+n>=a[i+1]+(n-i+1))
                ans++;
        ans++;
        cout<<ans<<endl;
        return 0;
    }
    
    
  • -1
    @ 2016-11-03 21:36:36

    set超时一点点, 自己用treap改了个水过了, 发一发题解:

    c++
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <string>
    #include <vector>
    #include <stack>
    #include <ctime>
    #include <bitset>
    #include <cstdlib>
    #include <cmath>
    #include <set>
    #include <list>
    #include <deque>
    #include <map>
    #include <queue>
    #define Max(a,b) ((a)>(b)?(a):(b))
    #define Min(a,b) ((a)<(b)?(a):(b))
    using namespace std;
    typedef long long ll;
    typedef long double ld;
    const double eps = 1e-6;
    const double PI = acos(-1);
    const int mod = 1000000000 + 7;
    const int INF = 0x3f3f3f3f;
    const int seed = 131;
    const ll INF64 = ll(1e18);
    const int maxn = 300000 + 10;
    int T,n,m,a[maxn];
    struct node {
        node *ch[2];
        int r, v, maxv;
        node(int v=0):v(v) {
            r = rand();
            ch[0] = ch[1] = NULL;
            maxv = v;
        }
        int cmp(int x) const {
            if(x == v) return -1;
            return x < v ? 0 : 1;
        }
        void maintain() {
            maxv = v;
            if(ch[1] != NULL) maxv = max(maxv, ch[1]->maxv);
        }
    } *g;
    void rotate(node* &o, int d) {
        node* k = o->ch[d^1];
        o->ch[d^1] = k->ch[d];
        k->ch[d] = o;
        o->maintain();
        k->maintain();
        o = k;
    }
    void insert(node* &o, int x) {
        if(o == NULL) o = new node(x);
        else {
            int d = (x < o->v ? 0 : 1);
            insert(o->ch[d], x);
            if(o->ch[d]->r > o->r) rotate(o, d^1);
        }
        o->maintain();
    }
    void remove(node* &o, int x) {
        int d = o->cmp(x);
        if(d == -1) {
            node* u = o;
            if(o->ch[0] != NULL && o->ch[1] != NULL) {
                int d2 = (o->ch[0]->r > o->ch[1]->r ? 1 : 0);
                rotate(o, d2);
                remove(o->ch[d2], x);
            }
            else {
                if(o->ch[0] == NULL) o = o->ch[1];
                else o = o->ch[0];
                delete u;
            }
        }
        else remove(o->ch[d], x);
        if(o != NULL) o->maintain();
    }
    void removetree(node* &x) {
        if(x->ch[0] != NULL) removetree(x->ch[0]);
        if(x->ch[1] != NULL) removetree(x->ch[1]);
        delete x;
        x = NULL;
    }
    int main() {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        int ans = 0;
        sort(a+1, a+n+1);
        for(int i = 2; i <= n; i++) {
            insert(g, a[i]+n-i+1);
        }
        for(int i = 1; i <= n; i++) {
            int cur = g->maxv;
            if(cur <= a[i]+n) ++ans;
            if(i == n) continue;
            remove(g, a[i+1]+n-i);
            insert(g, a[i]+n-i);
        }
        printf("%d\n", ans);
        return 0;
    }
    
    
    
  • 1

信息

ID
1988
难度
5
分类
(无)
标签
(无)
递交数
496
已通过
166
通过率
33%
被复制
1
上传者