最近看到了一个关于差分的题目。
题目描述
给定一个长度为n的数列a1,a2,…,an，每次可以选择一个区间[l,r]，使得这个区间内的数都加1或者都减1。
请问至少需要多少次操作才能使数列中的所有数都相等？在保证最少次数的前提下，最后的情况有多少种？
输入格式
第一行一个正整数n。
接下来n行，每行1个整数，第i+1行的整数代表ai。
输出格式
两行，每行一个整数。
第一个整数代表最少操作次数。
第二个整数代表最终会得到多少种结果。
输入输出样例
输入
4
1
1
2
2
输出
1
2
1.这个题目刚开始写的时候也是没有头脑，后面看了一些题解，发现这是用到了差分。差分通俗来说，就是另外开一个数组，数组里面记录的是a数组里面连续的俩个相差的值，就是后面的那个减去前面的那个，代码就是b[i]=a[i]-a[i-1];（b数组就是记录相差的值）
2.为什么要这么做呢，因为记录相差的值可以看出来，它们在区间内要减去多少次才能使它们成为一个每个值相等的数列。
3.这道题要怎么解决？那就是让b数组成为一个所有数为0的序列。它们就会相等。
4.当然我们是不知道它们（a数组）最后全部变成哪一个数使它们相等。b数组为0了，就是代表a数组全部相等。
5.使b数组减少或者增加，负数加成0，正数减成0，要一起搞，这样才能保证最少操作次数。我们记录下正数之和和负数之和（记录负数的相反数之和），然后看哪一个大，大的那个是最少操作次数。因为正数和负数会抵消啊，剩下的就是正数或者负数要单独搞。正数之和和负数之和谁最大就是最少操作次数。
6.那如何算出有多少个数列呢，数列个数为 正数之和减去负数之和（也是负数的相反数之和）的绝对值加1。
7.为什么是这样，差分数组首先和原数组是没有关系的，差分数组最终可能会变成只剩下一个不为0，在这个情况下，我们改变a数组的值（比如加1，减1），使他们除了差分数组那个不为0的区间不改变，那么它们差分还是为0，这个时候差分数组不为0的区间就可以少减去一次（当其他数往上或者往下时，那个b数组不为0的值也就会相应的变化），但是最少操作数不变！！！
8.为什么要+1，因为我们可以使b数组里面那个不为0区间（是包括对应a数组后面所有的值）加1或者减1，使b数组对应不为0的区间和前面差分为0的a数组值一样。还可以，一起改变前面差分为0的a数组，不改变差分不为0的区间。所以一共有正数之和减去负数之和（负数的相反数之和）的绝对值加1。
代码如下：
#include<stdio.h>
#include<math.h>
int main()
{
int a[100]={0},b[100]={0},n,i,j,max=0,min=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=2;i<=n;i++)//要从2开始
{
b[i]=a[i]-a[i-1];
if(b[i]>0) max+=b[i];
if(b[i]<0) min-=b[i];
}
printf("%d\n",max>min?max:min);
printf("%d\n",abs(max-min)+1);
return 0;
}
题目描述
输入 n个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,an，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。
输入格式
第一行 2个整数 n 和 m，表示数字个数和询问次数。
第二行 n个整数，表示这些待查询的数字。
第三行 m个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
输出一行，m 个整数，以空格隔开，表示答案。
输入输出样例
输入
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出
1 2 -1
这个题目是二分思想。二分查找前提必须是有序数组。
代码如下：（这个代码洛谷给了80分最后一个超时了，大家看看就好）
#include<stdio.h>
int slove(long long a[1000005],long long x,long long left,long long right)
{
if(left>right) return -1;
if(x==a[left])
{
while(left&&x==a[left]) left--;
return left+1;
}
if(x==a[right])
{
while(right&&x==a[right]) right--;
return right+1;
}
int mid=(left+right)/2;
if(x<a[mid]) slove(a,x,left,mid-1);
else if(x==a[mid])
{
while(mid&&x==a[mid]) mid--;
return mid+1;
}
else slove(a,x,mid+1,right);
}
int main()
{
long long n,m,a[1000005],b[1000005],i,j,x;
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(i=0;i<m;i++)
{
scanf("%lld",&x);
b[i]=slove(a,x,1,n);
}
for(i=0;i<m;i++)
printf("%d ",b[i]);
}
题目描述
话说我们家小谭啊，他特别的好吃懒做，对于吃还很挑剔，有一天他得到了一堆的饮料，他就想要喝掉这些饮料，但是他喝饮料有个特殊的习惯，那就是不喜欢连续两次喝相同的饮料，小谭不知道是否存在一种喝饮料的顺序使得他能够喝完所有的饮料，所以他请你帮他写个程序来测一测。
输入
多组输入
每组第一行输入一个n ( 0 < n <= 10 ) 代表饮料的种类数量，接下来的一行有n个数，代表每种饮料的数量 p（p < 1e9 )
输出
如果存在一种喝饮料的顺序能够使小谭喝完所有的饮料就输出 yes 否则输出 no 。
样例输入 复制
3
4 1 1
5
5 4 3 2 1
样例输出 复制
no
yes
1.这个题目是一个思维题，在排列组合里面有一种方法，叫做插空法。
2.利用这个思维，我们很容易的知道我们只要拿出最大相同的饮料数-1和剩下饮料的总和比较，如果剩下的饮料能够大于最大饮料数-1即可。
给大家示范一下
3.我们只需要填充最大的饮料数，就是从5中间隔开的，其他肯定不会是相同。
献上代码：
#include<stdio.h>
int main()
{
double sum,max;
long long n,a[15],i,j;
while(~scanf("%lld",&n))
{
sum=0;max=0;
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
if(max<a[i]) max=a[i];
}
if((sum-max)>=max-1) printf("yes\n");
else printf("no\n");
}
return 0;
}
题目描述
辅导群中出了个爱装逼的人。这人代号叫做琴兽。琴兽有个缺点，就是特别怕纯素数。所以为了让我们的辅导群更加健康，让我们一起来用纯素数来黑他吧。
纯素数的定义：一个数比如3797他是一个素数，去掉最后一位后379他也是素数，再去掉一位后37他也是素数，再去掉一位3他还是素数。所以他是一个纯素数，此时因为3797是4位数，所以说他是4维的。
输入
首先是一个 0 < n <= 5000 代表有有多少组数据
接下来的每一行输入一个 0 < t < 9
输出
对于每组数据输入所有的 t 维纯素数，按从小到大的顺序
样例输入
1
1
样例输出
2
3
5
7
1.这个题目如果我们递归去求肯定会时间超限，因为会在递归中一步一步判断几维的时候，很多都是不成立，半途而废的，大大耗费了时间。
2.这个题目较为特殊，一直去掉最后一位，它仍旧是一个素数，那么我们可以先从1维开始，算出1维的素数，然后再在把原本的1维数乘以10加上1~9的数字，看它是不是素数。
3.用一个二维数组记下每一维的素数，这样下次就可以直接用，时间就会短很多。
献上代码：
#include<stdio.h>
long long a[10][100];
int sushu(long long n)
{
if(n==1) return 0;
long long i;
for(i=2;i*i<=n;i++)
if(n%i==0) return 0;
return 1;
}
int slove()
{
int t,i,j,k,l=0;
long long s,ts;
for(i=1;i<=9;i++)
{
if(sushu(i)) a[1][l++]=i;
}
for(i=2;i<9;i++)
{
l=0;
for(j=0;a[i-1][j]!=0;j++)
{
s=a[i-1][j];
for(k=1;k<=9;k++)
{
ts=s*10+k;
if(sushu(ts))
{
a[i][l++]=ts;
}
}
}
}
}
int main()
{
int n,i,j,t;
slove();
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&t);
for(j=0;a[t][j]!=0;j++)
{
printf("%lld\n",a[t][j]);
}
}
}
题目描述
某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入
输入数据只有一行，该行包含若干个数据，之间用半角逗号隔开，表示导弹依次飞来的高度（导弹最多有 20 枚，其高度为不大于 30000 的正整数）。
输出
输出数据只有一行，该行包含两个数据，之间用半角逗号隔开。第一个数据表示这套系统最多能拦截的导弹数；第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。
样例输入
389,207,155,300,299,170,158,65
样例输出
6,1
1.这个题目是要求最长递减序列，另外开一个数组b，总是记下对应a[i]前面有多少个比a[i]大de的数（第一个肯定就没有）但是我们要包括它，算成1，求最长递减序列嘛。
2.遍历它前面所有的元素，如果前面有比它大的元素（这个元素暂且叫做qm），那么就加上b数组中qm（qm在b数组里面存储的比qm大的个数）的值。在这个过程中，用max记下最长子序列。
3.那么如何判断还需要几个系统呢，我们用另外一个数组来记下（就叫c数组吧）。在c数组中我们记录有几个递减的序列就可以知道，还需要几套系统。因为成递减序列，我们只需要每次都去刷新最小值即可，如果不在第一个系统中，也就是说中途遇到一个值大于第一个系统当前的最小值，就说明出现了一个新的递减序列，我们就需要把系统数k++。
献上代码：
#include<stdio.h>
int main()
{
int a[25],i,j,k,n=0,tx[25]={0},max=0,count=0,lzy[25];
while(~scanf("%d,",&a[n]))
{
n++;
}
for(i=0;i<n;i++)
{//因为统计的都是前面比它大的，到后面会成为一个递减的数列
tx[i]=1;//包括它自己有一个，初始化
for(j=0;j<i;j++)//遍历前面的
{
if(a[j]>=a[i])//前面有比它大的
{
tx[i]=tx[i]>tx[j]+1?tx[i]:tx[j]+1;//统计包括a[i]的大小
}
}
if(max<tx[i]) max=tx[i];
}
for(i=0;i<n;i++)
{//如果lzy数组里面存放的大于a[i]则停下来，刷新它
for(k=0;k<count&&lzy[k]<a[i];k++);//找是和哪个序列递减
lzy[k]=a[i];
//lzy数组里面第一个保留的是第一个序列的最小值，并且一直在往下刷新
//如果遇到中途比它大说明出现了新的递减序列
if(k>=count) count++;//如果遍历完了k，还是找不到序列递减的值，则加1，并且存下来
}
printf("%d,%d\n",max,count-1);
return 0;
}
题目描述
zjz学长参加了一项考试，但是考试只给出来成绩，没有给出排名，zjz学长想请问你他如果是x分他会是多少名
输入
第一行输入两个数n和m，代表有n个人参加了考试 （1 <= n <= 1e5），m(1<=n<=1e5)次询问
第二行输入n个数，每个数ai，代表第 i 个人的成绩 （0 <= a[i] <= 1e5）
第三行输入m个数x，你需要回答zjz学长如果是x分，他应该排多少名。 (保证至少存在一个a[i]=x)
保证x是数组a中的某个数
输出
输出m行，每行只输出一个数。
样例输入
10 2
1 2 3 4 5 6 7 8 9 10
1
2
样例输出
10
9
1.这个题目也是用到了前缀和，然后还要桶排序。
2.我们在输入的时候就把它放入一个为它的值的桶，把桶的值++，在这个过程中刷新最大值max的值（这个后面要用到）。
3.从最大值开始，（因为排名是按降序来的），b数组里面max这个分数就是对应max那个桶的值。（才能往前循坏，b数组才能从后面得到排名）每次b[i]都是等于排在前面的加上当前分数a[i]在桶里面的值，因为这个学长永远排在最后。
4.最后输出的时候，只需要看这个分数c[i]在b数组里面的值即可。
献上代码：
#include<stdio.h>
int a[100100],b[100100],c[100100];
int main()
{
int n,m,i,score,x,max=0;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%d",&score);
if(max<score) max=score;
a[score]++;
}
b[max]=a[max];
for(i=max-1;i>=0;i--)
{
b[i]=a[i]+b[i+1];
}
for(i=0;i<m;i++)
{
scanf("%d",&c[i]);
}
for(i=0;i<m;i++)
{
printf("%d\n",b[c[i]]);
}
return 0;
}