水题四道。

我的

水题四道--题目目录

问题 A: 依次输出第k小整数

 代码1

问题 B: 第k小整数(knumber)

 代码2

树的统计

 代码3

 枪声问题

 代码4

---

问题 A: 依次输出第k小整数

现有n个正整数，n≤10000，要求出这n个正整数中的第1小的整数，第2小的整数，第3小的整数，依次类推，直到将所有的整数都找完为止（小从到大），正整数均小于30000 。

第1行为n，
第2行开始为n个正整数的值，整数间用空格隔开。

第一行依次输出

1 第1小的整数

2 第2小的整数

3 第3小的是谁

……            (中间用一个空格分隔)

8 
8 6 8 6 1 3 6 9

1 1
2 3
3 6
4 8
5 9

其实就是第k小的铺垫。

 代码1

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,i,a[10005],t;
main(){
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(i=1;i<=n;i++)
        if(a[i]!=a[i+1])
            cout<<++t<<" "<<a[i]<<"\n";
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,i,a[10005],t;
main(){cin>>n;for(i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(i=1;i<=n;i++)if(a[i]!=a[i+1])cout<<++t<<" "<<a[i]<<"\n";
}

问题 B: 第k小整数(knumber)

现有n个正整数，n≤10000，要求出这n个正整数中的第k个最小整数（相同大小的整数只计算一次），k≤4000，正整数均小于30000 。

第1行为n和k，第2行开始为n个正整数的值，整数间用空格隔开。

第k个最小整数的值；

10  3
1 3 3 7 2 5 1 2 4 6

3

........

 代码2

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,i,a[10005],k,b[10005],t;
main(){
    cin>>n>>k;
    for(i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(i=1;i<=n;i++)if(a[i]!=a[i+1])b[++t]=a[i];
    sort(b+1,b+1+t);
    cout<<b[k];
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,i,a[10005],k,b[10005],t;
main(){cin>>n>>k;for(i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(i=1;i<=n;i++)if(a[i]!=a[i+1])b[++t]=a[i];sort(b+1,b+1+t);cout<<b[k];
}

树的统计

   某条街边上有长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些地方要进行改造，需要改造的地方用它们在数轴上的起始点和终止点表示。已知任一范围的起始点和终止点在数轴上的位置都是整数，各范围之间可能有重合的部分。现在要把给定范围中的树（包括范围的端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

如下图中，L=12，有4个范围要改造，分别是2—5,  3—6,  6—8,  7—11

则马路上还有3棵树。分别是第0、1、12位置上的树，其他树都被移走了。


 

 从文件tongji.in读入数据，文件中的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域范围的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域范围的起始点和终止点在数轴上的值。

结果输出到文件tongji.out中，只有一个整数，表示马路上剩余的树的数目。

12  4
2  5
3  6
6  8
7  11

3

离散化呗。

 代码3

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,i,x,y,f[100005],s;
main(){
    cin>>n>>m;
    for(i=1;i<=m;i++){cin>>x>>y;f[x]++;f[y+1]--;}
    for(i=0;i<=n;i++)f[i]=f[i-1]+f[i];
    for(i=0;i<=n;i++)if(f[i]==0)s++;
    cout<<s;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,i,x,y,f[100005],s;
main(){cin>>n>>m;for(i=1;i<=m;i++){cin>>x>>y;f[x]++;f[y+1]--;}for(i=0;i<=n;i++)f[i]=f[i-1]+f[i];for(i=0;i<=n;i++)if(f[i]==0)s++;cout<<s;
}

 枪声问题

小明和小李同时参加了射击比赛，比赛规则是这样的，每次两人同时射击，每个人有S枚子弹进行射击，第1秒两人同时打出第一枚子弹，以后的s-1子弹可以自己根据一定的间隔时间打出，设小明后面的子弹每隔t1秒打出一枚子弹，小李后面的子弹每隔t2秒打出一枚子弹，如t1=2时，则后面子弹打出的时刻分别为4,7，10,13，…。如果某一时刻两人同时打出子弹，则只能听到一次响声，现在要你统计这两个人的比赛中共能听到几次枪声。

从文件gan.in中读入数据，文件中共有三行，第一行表示S的值(S<100)，第二行是正整数t1的值（t1<=20），第三行是正整数t2的值（t2<=20）。

结果输出到gan.out 中，只有一个数，表示能听到的枪声的次数。

5
2
3

8

 代码4

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
int n,m,i,a[20010],x,y,t,w,b[20010],c[20010],j,s,d[20010],e[20010];
main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>x>>y;
    t=1;i=1;
    while(i<=n){b[i]=t;t+=(x+1);i++;}
    w=1;i=1;
    while(i<=n){c[i]=w;w+=(y+1);i++;}
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(b[i]!=c[j])s++;
    cout<<n*2-(n*n-s);
}

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
int n,m,i,a[20010],x,y,t,w,b[20010],c[20010],j,s,d[20010],e[20010];
main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>n>>x>>y;t=1;i=1;while(i<=n){b[i]=t;t+=(x+1);i++;}w=1;i=1;while(i<=n){c[i]=w;w+=(y+1);i++;}for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(b[i]!=c[j])s++;cout<<n*2-(n*n-s);
}