删数问题
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：test.in 输出文件名：test.out
问题描述
键盘输入一个高精度的正整数n（<=240位），去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案，使得剩下的数字组成的新数最小。
输入格式
n
s输出格式
最后剩下的最小数
样例输入
178543
4样例输出
13
分析：
每次删第一个比后一位大的数，如果没有则删除最后一位。位数越高，位置越重要，所以要从最高位开始循环，每次删掉一个数之后，就相当于把前面的数都朝后移了一位，所以删的数前面的数会取代它，所以要使前面的数比删的数小，而在一个递增的序列中，越朝后数越大，那删掉后给整体减的值也就大。上面的综合起来就成了这题的贪心法则。
程序也很简单，用string的erase函数擦除，很方便。
一开始不知道有前导0，错了。
源代码：
#include <bits/stdc++.h>
using namespace std;
string n;
int s;
int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
getline(cin,n);
cin >> s;
int nl = n.length();
int i = 0, js = 0;
while(i < nl){
if(n[i+1] < n[i]||i==nl-1){
n.erase(i,1);
nl--;
i = 0;
if( ++js == s) break;
continue;
}
i++;
}
while(n[0]=='0' && n.length() >= 2) n.erase(0,1);
cout << n << endl;
fclose(stdin);fclose(stdout);
return 0;
}
活动选择
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：test.in 输出文件名：test.out
问题描述
假设有一个需要使用某一资源的n个活动组成的集合S，S＝｛1，…，n｝。该资源一次只能被一个活动所占用，每一个活动有一个开始时间bi和结束时间ei（bi<=ei）。若bi>ej或者bj>ei，则活动兼容。
你的任务是：选择由互相兼容的活动组成的最大集合中元素的个数。输入格式
共n＋1行，其中第1行为n，第2行到第n+1行表示n个活动的开始时间和结束时间（中间用空格隔开），格式为：
n b1 e1 …… bn en （注：所有数据不超过整型）输出格式
一个整数，表示可以兼容活动的最大个数。
样例输入
11
3 5 1 4 12 14 8 12 0 6 8 11 6 10 5 7 3 8 5 9 2 13样例输出
4
分析：这题的贪心策略很好想。我们应当选择结束尽可能早的活动。
很明显地对于两个结束时间Ti、Tj，Ti < Tj， Tj结束后能选的活动，Ti结束了也肯定能选，但Ti结束能选的，Tj就不一定能选。
那么程序也就得出来了：先按照活动结束的时间排序，然后每一次找在这之后开始的，结束最早的活动。
源代码：
#include <bits/stdc++.h>
using namespace std;
int n, ans = 1;
struct nod{
int b, e;
}a[10000010];
bool cmp(nod p, nod q){
return p.e < q.e || (p.e == q.e && p.b < q.b);
}
int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i].b >> a[i].e;
sort(a+1,a+n+1,cmp);
int end = a[1].e;
for(int i = 1; i <= n; i++){
if(a[i].b > end){
ans++;
end = a[i].e;
}
}
cout << ans << endl;
fclose(stdin);fclose(stdout);
return 0;
}
排队接水
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：test.in 输出文件名：test.out
问题描述
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti(<=100)，请编程找出这n(<=10000)个人排队的一种顺序，使得n个人的平均等待时间最小。
输入格式
共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
输出格式
平均等待时间(输出结果精确到小数点后两位)。
样例输入
10
56 12 1 99 1000 234 33 55 99 812样例输出
291.90
分析：这题的策略也很明显，按照生活经验也应该知道了。用时少的人排在前面。
注意，自己打水的时间也是算在等待时间里的。
假设一个人等水的时间为Ti,另一个是Tj，Ti<Tj，Ti在前时，平均时间是(2Ti+Tj)/2，Tj在前时，平均时间是(2Tj+Ti)/2，所以应该让时间少的排在前面。
程序用一个前缀和就做出来了。
源代码：
#include <bits/stdc++.h>
using namespace std;
int a[10010], n, s[10010];
double sum;
int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
sort(a+1,a+n+1);
for(int i = 1; i <= n; i++){
s[i] = s[i-1] + a[i];
sum += s[i-1];
}
cout << fixed << setprecision(2) << sum / n << endl;
fclose(stdin);fclose(stdout);
return 0;
}
智力大冲浪
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：test.in 输出文件名：test.out
问题描述
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!输入格式
共4行。
第1行为m，表示一开始奖励给每位参赛者的钱； 第2行为n，表示有n个小游戏； 第3行有n个数，分别表示游戏1到n的规定完成期限； 第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。输出格式
仅1行。表示小伟能赢取最多的钱。
样例输入
10000
7 4 2 4 3 1 4 6 70 60 50 40 30 20 10样例输出
9950
分析：看到题，首先想到的就是优先完成罚款较少的游戏，然后最好的策略肯定是恰好在期限结束时完成游戏，空出前面更加宝贵的时间（很明显，越靠前的时间单位越有价值，因为越朝前，可以满足的游戏期限就越多）。那怎样尽可能地控制时间呢？
我就想到了类似vh数组做标记的的方法，开一个t数组，用来记录某一时段是否被占用，程序实现类似于vh的开放定址，循环找空位。
源代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, t[510];
struct zhili{
int t, w;
}a[510];
bool cmp(zhili a, zhili b){
return a.w > b.w;
}
bool check(int tim){
while(tim > 0 && t[tim] != -1) tim--;
if(tim == 0) return false;
if(t[tim] == -1){
t[tim] = 1;
return true;
}
}
int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
cin >> m >> n;
for(int i = 1; i <= n; i++)
cin >> a[i].t;
for(int i = 1; i <= n; i++)
cin >> a[i].w;
sort(a+1,a+n+1,cmp);
memset(t,-1,sizeof(t));
for(int i = 1; i <= n; i++){
if(!check(a[i].t)) m -= a[i].w;
}
cout << m << endl;
fclose(stdin);fclose(stdout);
return 0;
}
*雇拥计划
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：test.in 输出文件名：test.out
问题描述
一位管理项目的经理想要确定每个月需要的工人，他当然知道每月所需的最少工人数。当他雇佣或解雇一个工人时，会有一些额外支出。一旦一个工人被雇佣，即使他不工作，他也将得到工资。这位经理知道雇佣一个工人的费用，解雇一个工人的费用和一个工人的工资。现他在考虑一个问题：为了把项目的费用控制在最低，他将每月雇佣多少个工人。
输入格式
共三行。第一行为月数n(不超过12)。
第二行含雇佣一个工人的费用，一个工人的工资和解雇一个工人的费用（<=100）。 第三行含n个数，分别表示每月需要的工人数（<=1000）。每个数据之间有一个空格隔开输出格式
仅一行，表示项目的最小总费用。
样例输入
3
4 5 6 10 9 11样例输出
199
分析：
一开始没有思路，老师提醒之后，很快就想通了。
首先，在工人数不足时，肯定要购入工人，正好时就维持原状。
重点是在于工人多了时要不要解雇，解雇多少，怎样会解雇他呢？
当我不需要他的时候，就是以后永远用不到它了，当然要解雇他。如果中间隔了一段时间，又需要他了，就进行成本的预判：是当即解雇他，之后再重新招他成本高，还是一直留到需要他为止成本高呢，枚举月份判断就好了。
想出思路时觉得很简单，只是一写代码才发觉并不简单，上面只是说一个人，那多出几个人的时候解雇几个，留几个呢？代码想了很久也没有想出来，卡了很久，最后没有办法，只能去参考学长写的代码了。
思路大概一致，后面的枚举，还枚举了是否要解雇人员的个数。
源代码：#include<bits/stdc++.h>
using namespace std;
int hire,salary,fire,num[110],n;
int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
cin>>n;
cin>>hire>>salary>>fire;
for(int i=1;i<=n;i++)
cin>>num[i];
int cost=0,sum=0;
for(int i=1;i<=n;i++){
if(sum<=num[i]){
cost+=num[i]*salary+(num[i]-sum)*hire;
sum=num[i];
continue;
}
int k=sum-num[i];
cost+=num[i]*salary;
for(int j=1;j<=k;j++){
int next=n+1,cost1=fire;
for(int t=i+1;t<=n;t++)
if(num[t]>=num[i]+j){
next= t;
break;
}
if(next<=n) cost1+=hire;
int cost2=(next-i)*salary;
if(cost2<cost1) cost+=salary;
else cost+=fire,sum--;
}
}
cout<<cost<<endl;
return 0;
}
幂取模
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：mod.in 输出文件名：mod.out
问题描述
求a的b次方模k的值，a,b及k*k均是小于231的正整数。
输入格式
一行，三个用空格隔开的整数，a, b, k
输出格式
输出结果：a^b mod k = 余数（参见样例）
样例输入
2 10 7
样例输出
2^10 mod 7=2
提示
“mod”前后各有一个空格。
分析：似乎是标程，但是也是有道理的。
由于a、b的大小，直接写肯定会溢出，那么就要想办法缩小两个数的规模。我们知道：
ab mod c = (a mod c)b mod c
网上的证明，也很好懂：
所以在算a^b前可以将a先%c，但这对于c较大的情况仍是没有什么用。
之后又推得两个公式：
记k = a2 mod c
所以：1.如果b是偶数，那么求(k)b/2 mod c就可以了。
2.如果b是奇数，那么求 ((k)b/2 mod c * a) mod c 就可以了。
迭代进行该过程，就得到了快速幂算法。一次为O(b/2),两次为O(b/4)，迭代后则为O（logb）
源代码：
#include <bits/stdc++.h>
using namespace std;
long long a, b, k, sum = 1;
int main(){
freopen("mod.in","r",stdin);
freopen("mod.out","w",stdout);
cin >> a >> b >> k;
cout << a << '^' << b << " mod " << k << '=';
a %= k;
while(b > 0){
if(b % 2 == 1)
sum = (sum * a) % k;
b /= 2;
a = (a*a) % k;
}
cout << sum << endl;
fclose(stdin);fclose(stdout);
return 0;
}
循环比赛
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：match.in 输出文件名：match.out
问题描述
设有n个选手进行循环比赛，其中n = 2m，要求每名选手要与其他n-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行n - 1天，要求每天没有选手轮空。
输入格式
一个正整数m(2 <= n <= 6)
输出格式
样例形式的比赛安排表
样例输入
3
样例输出
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1分析：很简单的一道题，观察图案，会发现规律：将其从两条邻边中线分开，将其分为四部分，则左上，右下相同，左下，右上相同，都是左上加上2的某次方。而图形的左上部分还可以继续这样拆分。从最开始的一格做一个复制的函数，很容易就过了。
源代码：
#include <bits/stdc++.h>
using namespace std;
int m, b = 1, a[70][70];
void copy(int h, int l, int jia, int x, int y){
for(int i = h; i <= h+b-1; i++)
for(int j = l; j <= l+b-1; j++)
a[i][j] = a[i-x][j-y] + jia;
}
int main(){
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
cin >> m;
a[1][1] = 1;
for(int i = 1; i <= m; i++){
copy(1,b+1,b,0,b);
copy(b+1,1,b,b,0);
copy(b+1,b+1,0,b,b);
b *= 2;
}
for(int i = 1; i <= b; i++){
for(int j = 1; j <= b; j++)
cout << a[i][j] << ' ';
cout << endl;
}
fclose(stdin);fclose(stdout);
return 0;
}
【NOIP2001T】方程求解
时间限制：1.0s 内存限制：64.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：equation.in 输出文件名：equation.out
试题来源：NOIP
问题描述
有形如：ax^3+bx^2+cx+d=0 这样的一个一元三次方程。
输入格式
给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。
输出格式
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
样例输入
1 -5 -4 20
样例输出
-2.00 2.00 5.00
提示
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个根。
分析：因为答案在-100到100之间且答案只要精确两位，所以可以直接枚举，按照题目提示的方法来判断根的值。有就输出。
源代码：
#include <bits/stdc++.h>
using namespace std;
double a, b, c, d;
double f(double x){
return a*x*x*x+b*x*x+c*x+d;
}
int main(){
freopen("equation.in","r",stdin);
freopen("equation.out","w",stdout);
cin >> a >> b >> c >> d;
for(double i = -10000; i <= 10000; i++){
double x = i/100;
if(f(x+0.001)*f(x-0.001) < 0)
cout << fixed << setprecision(2) << x << ' ';
}
cout << endl;
fclose(stdin);fclose(stdout);
return 0;
}
光荣的梦想
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：dream.in 输出文件名：dream.out
问题描述
Prince 对他在这片大陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。在他动身之前，Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代，平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量，平衡瞬间即被打破。KB决定求助于你，帮助他完成这个梦想。
一串数列即表示一个世界的状态。 平衡是指这串数列以升序排列。而从一串无序序列到有序序列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。输入格式
第1行为数列中数的个数n（n <= 100000）
第2行为n个数（绝对值不超过100000）。表示当前数列的状态。输出格式
输出一个整数，表示最少需要交换几次能达到平衡状态。
样例输入
4
2 1 4 3样例输出
2
分析：一开始看到逆序对，首先想到的就是冒泡排序，于是就有了这个程序。但O(n^2)的算法显然无法通过100000的数据。超时，30分。
源代码：
#include <bits/stdc++.h>
using namespace std;
int n, a[100010], js;
int main(){
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i < n; i++){
for(int j = 1; j <= n-i; j++){
if(a[j] > a[j+1]){
swap(a[j],a[j+1]);
js++;
}
}
}
cout << js << endl;
fclose(stdin);fclose(stdout);
return 0;
}
分析：
从书上学了归并排序求逆序对。核心部分就是利用2个有序序列合成一个有序序列的O（n+m）的合并。
两个分前后顺序的序列，如果前一个序列的排头小于后一个序列的排头，由于第一个序列有序，所以这个序列里所有元素都大于第二个序列的排头，就产生了(第一个序列元素个数)个逆序对，将原本一整个序列一步步分解，就得到了最后的程序。
归并排序的复杂度是O(nlogn)，可以通过本题。
注意，最多有100000^2对逆序对，要开long long的。
源代码：
#include <bits/stdc++.h>
using namespace std;
int n, a[100010], linshi[100010];
long long ans;
void gb(int left, int right){
if(left >= right) return ;
int mid = (left + right) / 2;
gb(left,mid);
gb(mid+1,right);
int pos = left, i = left, j = mid + 1;
while(i <= mid && j <= right){
if(a[i] > a[j]){
ans += mid - i + 1;
linshi[pos] = a[j];
pos++; j++;
}
else{
linshi[pos] = a[i];
pos++; i++;
}
}
while(i <= mid){ linshi[pos] = a[i]; pos++; i++;}
while(j <= right){ linshi[pos] = a[j]; pos++; j++;}
for(int i = left; i <= right; i++) a[i] = linshi[i];
}
int main(){
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
gb(1,n);
cout << ans << endl;
fclose(stdin);fclose(stdout);
return 0;
}
【NOIP2015T】跳石头
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
输入文件名：stone.in 输出文件名：stone.out
试题来源：NOIP
问题描述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有N块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走M块岩石（不能移走起点和终点的岩石）。输入格式
输入文件名为stone.in。 输入文件第一行包含三个整数L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来N行，每行一个整数，第i行的整数Di（0 < Di < L）表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。输出格式
输出文件名为stone.out。
输出文件只包含一个整数，即最短跳跃距离的最大值。样例输入
25 5 2
2 11 14 17 21样例输出
4
提示
对于20%的数据，0 ≤ M ≤ N ≤ 10。 对于50%的数据，0 ≤ M ≤ N ≤ 100。
对于100%的数据，0 ≤ M ≤ N ≤ 50,000，1 ≤ L ≤ 1,000,000,000。分析：这题做初赛准备时做过，是二分答案题，算是目前我学的二分里比较难的。Mid为最短的跳跃距离的最大值，做一个函数来检查在这个值的情况下要移走多少块石头，如果少于或等于m，就说明这个值还有进一步提升的空间，将左端点移为mid，否则，右端点移为mid。
源代码：#include <bits/stdc++.h>
using namespace std;
int n, l, m, a[50010];
bool check(int mid){
int js = 0, p = 0;
for(int i = 1; i <= n; i++){
if(a[i] - p < mid)
js++;
else
p = a[i];
}
return js <= m;
}
int main(){
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
cin >> l >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i];
int le = 1, r = l+1, mid;
while(le + 1 < r){
mid = (le+r)/2;
if(check(mid))
le = mid;
else
r = mid;
}
cout << le << endl;
fclose(stdin);
fclose(stdout);
return 0;
}