# 106 条题解

• @ 2017-12-13 14:21:07
``````#include<cstdio>
#include<algorithm>
struct preson {
int id;
int w;
} pe[50010];
int E[11];
bool cmp(preson a,preson b) {
if(a.w!=b.w) return a.w>b.w;
else return a.id<b.id;
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
for(int i=1; i<=10; i++) scanf("%d", &E[i]);
for(int i=0; i<n; i++) {
scanf("%d", &pe[i].w);
pe[i].id=i+1;
}
std::sort(pe,pe+n,cmp);
for(int i=0; i<n; i++) pe[i].w+=E[i%10+1];
std::sort(pe,pe+n,cmp);
for(int i=0; i<k; i++) printf("%d ",pe[i].id);
return 0;
}
``````
• @ 2017-05-16 16:59:08
``````#include<stdio.h>
#include<stdlib.h>
#define MAX 50001
int cmp(const void *a, const void *b);

int E[11], T[MAX];
struct DATA {
int W, num;
}people[MAX];

int main()
{
int n, k, i, j;
int max_num, max_t;
scanf("%d%d", &n, &k);
for (i = 1; i <= n; i++)  people[i].num = i;
for (i = 1; i <= 10; i++)
scanf("%d", &E[i]);                        //额外权值E[i]
for (i = 1; i <= n; i++)
scanf("%d", &people[i].W);                 //初始权值W

qsort(people + 1, n, sizeof(people[0]), cmp);  //用快速排序对W和num同时排序

for (i = 1; i <= n; i++)                       //根据序号D增加E[i]额外权值
{
int extra = E[(i - 1) % 10 + 1];
T[people[i].num] = people[i].W + extra;    //注意这里的加法，T是总权值，people[i].W是编号为people[i].num的人对应的初始权值,extra是额外权值
}
for (j = 1; j <= k; j++)                       //比较k轮，找出T最大的前k个的编号并逐一打印
{
max_t = 0;
for (i = 1; i <= n; i++)
if (T[i] > max_t)
{
max_t = T[i];
max_num = i;
}
T[max_num] = 0;
printf("%d ", max_num);
}
getchar();
getchar();
return 0;
}

//cmp函数
int cmp(const void *a, const void *b)
{
struct DATA *aa = (struct DATA *)a;
struct DATA *bb = (struct DATA *)b;
if (aa->W != bb->W)
return(((bb->W)>(aa->W)) ? 1 : -1);        //这里是按照降序排序
else
return((aa->num) - (bb->num));
}

``````

强行快排

• @ 2017-08-18 23:03:14

#include<bits/stdc++.h>
struct peo{
int w,s;};
using namespace std;
bool com(const peo&a,const peo&b)
{if(a.w!=b.w)return a.w>b.w;
else return a.s<b.s;}
int main(){
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
int e[11];
for(int i=1;i<11;++i)
{cin>>e[i];}
peo a[n];
for(int i=1;i<n+1;++i)
{cin>>a[i].w;
a[i].s=i;}
sort(a+1,a+n+1,com);
for(int i=1;i<n+1;++i)
{a[i].w+=e[(i-1)%10+1];}
sort(a+1,a+n+1,com);
for(int i=1;i<k+1;++i)
{cout<<a[i].s<<' ';}
return 0;
}

• @ 2017-07-03 08:10:51

/*

一个双关键字排序就好了
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 50010

using namespace std;

int n,k,e[12];

struct node {
int w;
int id;
};
node a[MAXN];

x=0;int f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();}
x=x*f;
}

inline bool cmp(const node x,const node y) {
if(x.w==y.w) return x.id<y.id;
return x.w>y.w;
}

int main() {
for(int i=1;i<=n;i++) {
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) a[i].w+=e[(i-1)%10+1];
sort(a+1,a+1+n,cmp);
for(int i=1;i<=k;i++) printf("%d ",a[i].id);
return 0;
}

• @ 2021-09-23 13:35:45

# 这样的题目还是手写排序为好

``````#include <stdio.h>
#include <string.h>
#define MAXN 100000 + 10
#define min(a, b) ((a) < (b) ? (a) : (b))

struct people{
int w, d;
};

struct people temp[MAXN];
int e[11];
int judge(struct people *pep, int i, int j) {
if (pep[i].w > pep[j].w) return 1;
else if (pep[i].w == pep[j].w) return pep[i].d < pep[j].d;
return 0;
}
void merge(struct people *pep, int l1, int r1, int r2) {
int l2 = r1 + 1, i = l1, j = l2, k = 0;
while (i <= r1 && j <= r2) {
if (judge(pep, i, j)) temp[k++] = pep[i++];
else temp[k++] = pep[j++];
}
while (i <= r1) temp[k++] = pep[i++];
while (j <= r2) temp[k++] = pep[j++];
for (int i = 0; i < k; ++i) {
pep[i + l1] = temp[i];
}
}

void merge_sort(struct people *pep, int n) {
for (int seg = 1; seg < n; seg += seg) {
for (int start = 0; start < n - seg; start += seg + seg) {
merge(pep, start, start + seg - 1, min(n - 1, start + seg + seg - 1));
}
}
}
struct people pep[MAXN];
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= 10; ++i) scanf("%d", &e[i]);
for (int i = 0; i < n; ++i) {
scanf("%d", &pep[i].w);
pep[i].d = i + 1;
}
merge_sort(pep, n);
for (int i = 0; i < n; ++i) {
pep[i].w += e[i % 10 + 1];
}
merge_sort(pep, n);
for (int i = 0; i < k; ++i) {
//printf("%d %d\n", pep[i].d, pep[i].w);
printf("%d ", pep[i].d);
}
return 0;
}
``````
• @ 2018-07-25 13:29:59

很简单的一道题目，如果你使用sort函数的，主要是考察sort的用法，有两个注意：
（1）在排序中，如果两人的W[i]相同，编号小的优先，所以cmp用添加相等的处理；
（2）k是整数，因此可以是为0的，所以当0时，没有任何输出

``````#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int e[10];

struct People
{
int idx;
int w;
} arr[50002]; //n<=50 000

int cmp(People a, People b)
{
//return a.w > b.w;
if(a.w == b.w) return a.idx < b.idx;
else return a.w > b.w;
}

int main()
{
//freopen("input.txt", "r", stdin);

int i, j;
int n, k;
scanf("%d %d", &n, &k);

for(i = 0; i < 10; ++i) scanf("%d", &e[i]);
for(i = 0; i < n; ++i)
{
arr[i].idx = i;
scanf("%d", &arr[i].w);
}

sort(arr, arr + n, cmp);
//  for(i = 0;i < n; ++i) printf("%d %d,", arr[i].idx, arr[i].w);
//  printf("\n");

for(i = 0; i < n; ++i)
{
arr[i].w += e[i % 10];
}
sort(arr, arr + n, cmp);

if(k > 0)
{
printf("%d", arr[0].idx + 1);
for(i = 1; i < k; ++i) printf(" %d", arr[i].idx + 1);
printf("\n");
}

//fclose(stdin);

return 0;
}
``````
• @ 2018-03-02 13:41:05

#include<cstdio>
#include<algorithm>
using namespace std;
struct Person{
int id,w;
}p[10000001]; //结构体，方便些
int n,k,E[11];
bool cmp(Person,Person); //排序的函数
int main(){
scanf("%d%d",&n,&k); //输入
for(int i=1;i<=10;i++) scanf("%d",&E[i]);
for(int i=0;i<n;i++){
scanf("%d",&p[i].w);
p[i].id=i+1;
}
sort(p,p+n,cmp); //sort函数，需带algorithm头文件
for(int i=0;i<n;i++)
p[i].w+=E[i%10+1];
sort(p,p+n,cmp);
for(int i=0;i<k;i++) printf("%d ",p[i].id); //输出
return 0;
}
bool cmp(Person a,Person b){
if(a.w==b.w) return a.id<b.id;
return a.w>b.w;
}

• @ 2018-02-06 12:43:38
``````/*
描述看了一萬年，水題還能WA2次，給自己跪了
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 50000 + 10;
int n, k, e[15];

struct person{
int w, d;
} p[MAXN];

bool cmp(person p1, person p2){
return p1.w != p2.w ? p1.w > p2.w : p1.d < p2.d;
}

int main(){
cin.sync_with_stdio(false), cout.sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= 10; i++) cin >> e[i];
for (int i = 1; i <= n; i++) cin >> p[i].w, p[i].d = i;
sort(p + 1, p + 1 + n, cmp);
for (int i = 1; i <= n; i++) p[i].w += e[(i - 1) % 10 + 1];
sort(p + 1, p + 1 + n, cmp);
for (int i = 1; i <= k; i++) cout << p[i].d << " ";
cout << endl;
return 0;
}
``````
• @ 2017-08-03 13:46:18

啊哦，双关键字排序~

``````#include <bits/stdc++.h>
using namespace std;
const int maxn=50000+50;
struct fri
{
int num;
int w;
bool operator < (fri y){//重载小于运算符
if(this->w==y.w) return this->num<y.num;//当权值相等时按序号排序
return this->w>y.w;
}
}reny[maxn];

int main()
{
//freopen("input.txt","r",stdin);
int e[11];
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=10;i++)
scanf("%d",&e[i]);
for(int i=1;i<=n;i++){
reny[i].num=i;
scanf("%d",&reny[i].w);
}
sort(reny+1,reny+n+1);
for(int i=1;i<=n;i++)
reny[i].w+=e[(i-1)%10+1];
sort(reny+1,reny+n+1);
for(int i=1;i<=k;i++)
printf("%d ",reny[i].num);
return 0;
}

``````
• @ 2017-04-02 11:44:51

//唉，辣鸡win10都不能用pascal，我又那么懒不用自测，害我便提交便改错。。。
总之就是个双关键字快排
50分的算法就是不用双关键字快排；
100分的就是把你快排部分改一改：

``````      while (w[i].num>k)  do inc(i);
while (w[j].num<k） do dec(j);
``````

改成

``````    while (w[i].num>k) or ((w[i].num=k) and (w[i].bian<mid)) do inc(i);
while (w[j].num<k) or ((w[j].num=k) and (w[j].bian>mid)) do dec(j);
//mid 是编号（bian）的中间项 k 则是num的
```//伪代码稍微image一下应该懂得吧！！！
*顺便题意有些难以理解，是说读入后由大到小排序，**介事实上是把此时的数组均匀分成10份，第i份加e【i】的权值**

``````
• @ 2017-04-02 11:45:27
``````type gdc= record
num,bian:longint;
end;
var
n,k1,i,ed,bg,k:longint;
e:array[1..10] of longint;
w:array[1..100000] of gdc;
procedure qs(x,y:longint);
var
k,i,j,mid:longint;
tmp:gdc;
begin
i:=x;j:=y;k:=w[(x+y) div 2].num;mid:=w[(x+y) div 2].bian;
while i<=j do
begin
while (w[i].num>k) or ((w[i].num=k) and (w[i].bian<mid)) do inc(i);
while (w[j].num<k) or ((w[j].num=k) and (w[j].bian>mid)) do dec(j);
if (i<=j) then
begin
tmp:=w[i];
w[i]:=w[j];
w[j]:=tmp;
inc(i);
dec(j);
end;
end;
if (i<y) then qs(i,y);
if (x<j) then qs(x,j);
end;
begin
for i:= 1 to 10 do
for i:= 1 to n do
begin
w[i].bian:=i;
end;
qs(1,n);
for i:= 1 to n do
begin
w[i].num:=w[i].num+e[((i-1) mod 10) +1];
end;
qs(1,n);

for i:= 1 to k1  do
begin
write(w[i].bian,' ');
end;

end.
``````
• @ 2018-09-03 14:31:15

#include <iostream>
#include <algorithm>

using namespace std;

struct person{
int weight;
int index;
} people[50005];

void sortW(int l, int r) {
if (l >= r) return;
int i = l;
int j = r;
int w = people[i].weight;
int tmpi = people[i].index;
while (i < j) {
while ((i < j) && ((people[j].weight < w) || ((people[j].weight == w) && (people[j].index > tmpi)))) j--;
{
people[i].weight = people[j].weight;
people[i].index = people[j].index;
}
while ((i < j) && ((people[i].weight > w) || ((people[i].weight == w) && (people[i].index < tmpi)))) i++;
{
people[j].weight = people[i].weight;
people[j].index = people[i].index;
}
}
people[i].weight = w;
people[j].index = tmpi;
sortW(l, j - 1);
sortW(i + 1, r);
}

int main() {
int e[15];
int n, k;
cin >> n >> k;
for (int i = 1; i <= 10; i++) {
cin >> e[i];
}
for (int i = 1; i <= n; i++) {
cin >> people[i].weight;
people[i].index = i;
}
sortW(1, n + 1);
for (int i = 1; i <= n; i++) {
people[i].weight += e[(i - 1) % 10 + 1];
}
sortW(1, n + 1);
for (int i = 1; i <= k; i++) {
cout << people[i].index << ' ';
}

return 0;
}

• @ 2018-05-25 20:02:49

简单粗暴，懒得想其他的。。。

``````#include<bits/stdc++.h>
using namespace std;
long long n,k,e[11];
struct node{
int val;
int num;
}w[50001];
bool my_comp(node a,node b){
if(a.val!=b.val) return a.val>b.val;
else return a.num<b.num;
}

int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=10;++i) scanf("%d",&e[i]);
for(int i=1;i<=n;++i) scanf("%d",&w[i].val),w[i].num=i;
sort(w+1,w+n+1,my_comp);
for(int i=1;i<=n;++i){
w[i].val+=e[(i-1)%10+1];
}
sort(w+1,w+n+1,my_comp);
for(int i=1;i<=k;++i) printf("%d ",w[i].num);
return 0;
}
``````
• @ 2017-11-17 14:36:09
``````#include <iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define FOR(i,x,y) for(i=x;i<=y;++i)
#define maxa 50000+100
using namespace std;
int e[13];
struct node
{
int w,p1,p2;
}p[maxa];
bool comp(node a,node b)
{
return a.w>b.w;
}
bool comp1(node a,node b)
{
if(a.w!=b.w)
return a.w>b.w;
else
return a.p1<b.p1;
}
int main()
{
int n,k,i;
cin>>n>>k;
FOR(i,1,10)
cin>>e[i];
FOR(i,1,n)
{
cin>>p[i].w;
p[i].p1 = i;
}
sort(p+1,p+n+1,comp1);
FOR(i,1,n){
p[i].w+=e[(i-1)%10+1];
}
sort(p+1,p+n+1,comp1);
FOR(i,1,k)
{
cout<<p[i].p1<<" ";
}
}

``````
• @ 2017-11-12 20:21:01

也可以用优先队列,比较好看

``````#include <cstdio>
#include <queue>

using namespace std;

struct person {
int id;
int weight;

friend bool operator<(person a, person b) {
if (a.weight == b.weight) return a.id > b.id;
return a.weight < b.weight;
}
};

int main() {
int n, k, E[11];
priority_queue<person> q,q1;
scanf("%d %d", &n, &k);
for (int i = 1; i <= 10; i++) scanf("%d", E + i);
for (int i = 1, w; i <= n; i++) {
scanf("%d", &w);
q.push(person {id:i, weight:w});
}

for (int i = 1; i <= n; i++) {
person tmp = q.top();
tmp.weight += E[(i-1)%10+1];
q.pop();
q1.push(tmp);
}
for(int i=1;i<=k;i++){
person tmp = q1.top();
printf("%d ",tmp.id);
q1.pop();
}
printf("\n");
}
``````
• @ 2017-07-11 22:33:07

简单的双关键字排序，，但是我不知道是被东方的神秘力量控制了还是怎么的题目一直看不懂……，交了7，8次还错。最后绕回来发现最初的写法好像是对的……程序就不发了，我自己也似董非董……手动滑稽

• @ 2018-01-27 15:02:33

似董非董，江信江疑，你是一位真正的粉丝😂

• @ 2016-11-29 14:45:59
``````#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iterator>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <cctype>
#include <string>

using namespace std;

struct anode
{
int bianhao;
int quanzhi;
int xuhao;
int leibie;
};

bool cmp(anode const &x,anode const &y)
{
if(x.quanzhi==y.quanzhi){return x.bianhao<y.bianhao;}
else{return x.quanzhi>y.quanzhi;}
}

int main()
{
int n,k;
cin>>n>>k;

int e[11];
for(int i=1;i<=10;i++){cin>>e[i];}

anode a[50050];
for(int i=1;i<=n;i++){a[i].bianhao=i;cin>>a[i].quanzhi;}

sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
a[i].xuhao=i;
a[i].leibie=(a[i].xuhao-1)%10+1;
a[i].quanzhi+=e[a[i].leibie];
}

sort(a+1,a+1+n,cmp);

for(int i=1;i<=k;i++){cout<<a[i].bianhao<<' ';}

return 0;
}
``````
• @ 2016-03-18 12:49:18

第一次编号和序号弄混了
```pascal
var a:array[0..50001,1..2] of longint;
e:array[1..10] of longint;
n,k:longint;
i:longint;

procedure qsort(b,e:longint);
var temp,x,t,i,j:longint;
begin
if b<e then begin
x:=random(e-b)+b;
temp:=a[x,1];a[x,1]:=a[e,1];a[e,1]:=temp;
temp:=a[x,2];a[x,2]:=a[e,2];a[e,2]:=temp;
x:=a[e,1];t:=a[e,2];i:=b-1;
for j:=b to e-1 do
if (a[j,1]>x) or ((a[j,1]=x) and (a[j,2]<t)) then begin
inc(i);
temp:=a[j,1];a[j,1]:=a[i,1];a[i,1]:=temp;
temp:=a[j,2];a[j,2]:=a[i,2];a[i,2]:=temp;
end;
a[e,1]:=a[i+1,1];a[i+1,1]:=x;
a[e,2]:=a[i+1,2];a[i+1,2]:=t;
qsort(b,i);
qsort(i+2,e);
end;
end;

begin
randomize;
for i:=1 to 10 do read(e[i]);
for i:=1 to n do begin
a[i,2]:=i;
end;
qsort(1,n);
for i:=1 to n do begin
inc(a[i,1],e[(i-1) mod 10+1]);
end;
qsort(1,n);
for i:=1 to k do write(a[i,2]:6);
end.
```

• @ 2016-02-29 13:23:21
``````#include<iostream>
#include<algorithm>
using namespace std;
struct leaf{
long long x,y,z;
}a[50000];
long long n,k,w[10],i;

bool cmp(leaf a,leaf b){
return (a.x>b.x) || (a.x==b.x && a.z<b.z);
}

int main(){
cin>>n>>k;
for (i=0;i<10;i++) cin>>w[i];
for (i=0;i<n;i++){
cin>>a[i].x;
a[i].z=i+1;
}
sort(a,a+n,cmp);
for (i=0;i<n;i++){
a[i].y=i;
a[i].x+=w[a[i].y%10];
}
sort(a,a+n,cmp);
for (i=0;i<k;i++){
cout<<a[i].z;
if (i+1==k) cout<<endl;
else cout<<' ';
}
return 0;
}
``````
• @ 2016-02-20 15:30:22

题目描述真是醉了。贴一个C++代码。
```
/* ***********************************************
Author :guanjun
Created Time :2016/2/20 14:30:54
File Name :vijosp1282.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 50000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;

struct node{
ll x;
int id;
}nod[maxn];
bool cmp(node a,node b){
if(a.x==b.x)return a.id<b.id;
else return a.x>b.x;
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int n,k;
cin>>n>>k;
int e[11];
for(int i=1;i<=10;i++)cin>>e[i];
for(int i=1;i<=n;i++){
cin>>nod[i].x;
nod[i].id=i;
}
// for(int i=1;i<=10;i++)cin>>e[i];
sort(nod+1,nod+1+n,cmp);
for(int i=1;i<=n;i++){
nod[i].x+=e[(i-1)%10+1];
}
sort(nod+1,nod+1+n,cmp);
for(int i=1;i<=k;i++){
cout<<nod[i].id<<" ";
}
cout<<endl;
return 0;
}

• @ 2015-08-04 15:51:36

模拟后简单排序即可

ID
1282

6

3786

983

26%

4