题目信息

众所周知，唐老师特别喜欢挑战难度很高的电子游戏，有一天他挑战了一款回合对战游戏，唐老师的阵地有N个哨塔，编号由1到N，且初始时每个哨塔有自己的血量，游戏开始后，敌军会对唐老师的阵地发起M轮进攻，每轮进攻都会对一些哨塔产生等量的伤害。且满足第i轮进攻会对编号Li到Ri的哨塔造成等量伤害Di，M轮进攻结束后，唐老师需要快速对血量最低的K座哨塔进行修补，若存在与第K座哨塔相同血量仍需要输出，输出的哨塔编号个数可能多余K个，由于哨塔特别多，所以请帮忙设计程序帮助唐老师快速的找出需要修补的哨塔的编号，输出编号按从小到大顺序。

输入格式：

第一行包含两个三整数N,M,K。

第二行包含N个正整数，表示编号1到N哨塔的血量。

接下来M行，每行包含三个整数L，R，D，表示一轮进攻对编号L到R的哨塔造成了D点伤害。

输出格式：

共一行，包含K个正整数，以空格分隔，表示需要修补的哨塔编号。

数据范围：

1≤N,M≤100000,

1≤L≤R≤N,

1≤K≤N,

1≤D≤1000,

1≤哨塔血量≤21亿,且M轮进攻后不存在哨塔血量小于等于0的情况。

输入样例：

7 3 6

500 500 500 500 500 500 500

1 7 100

2 3 50

3 5 200

输出样例：

1 2 3 4 5 6 7

参考代码

#include<iostream>

using namespace std;

const int N = 100010;

typedef struct Tower

{

	int idx;

	int hp;

}tower;

tower a[N];

int d[N];

bool ans[N];

inline void insert(int l,int r,int c)

{

	d[l]+=c;

	d[r+1]-=c;

}

int part(tower q[],int l,int r,int k)

{

	if(l == r) return q[l].hp;

	int key = q[l+r>>1].hp;

	int i=l-1,j=r+1;

	while (i < j)

	{

		do i++; while(q[i].hp<key);

		do j--; while(q[j].hp>key);

		if (i < j)

			swap(q[i],q[j]);

	}

	int llen = j-l+1;

	if( k<=llen)

		part(q,l,j,k);

	else

		part(q,j+1,r,k-llen);

	

}

int main()

{

	int n,m,k;

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1;i<=n;i++) 

	{

		a[i].idx = i;

		scanf("%d",&a[i].hp);

		insert(i,i,a[i].hp);

	}

	for(int i=1;i<=m;i++)

	{

		int l,r,d;

		scanf("%d%d%d",&l,&r,&d);

		insert(l,r,-d);

	}

	for(int i=1;i<=n;i++){

		a[i].hp = a[i-1].hp+d[i];

		//printf("%d ",a[i].hp);

	}

	//printf("\n");

	int khp = part(a,1,n,k);

	for(int i=1;i<=n;i++)

		if (a[i].hp <= khp)

			ans[a[i].idx] = true;

	for(int i=1;i<=n;i++)

		if(ans[i]) 

			printf("%d ",i);

	

	return 0;

	 

}

结语：

正在教孩子学习差分和快排算法，索性把二者结合出一道题，让他痛快地练习两个算法。

没准这题能加入到下次CSP呢~