189 8069 5689
贪心不像是一种算法，更像是一种思维方式。
对于以下习题，笔者不禁发出深深感慨：这能算贪心？
LGP1199
解题思路构造出几种情况后就能猜想到：只要保证小涵所选的武将A，能使得与武将A默契值第二大的那个数大即可。但并没有构造出计算机赢的情况，于是乎抱着骗分的心态交了前面的猜想，然后居然AC了？！
具体博弈论题解可查看洛谷。（绝对不是因为笔者太蒻看不懂QAQ
#includeusing namespace std;
const int maxn=505;
int a[maxn][maxn];
int n;
int main(){cin>>n;
for (int i=1; ifor (int j=i+1; j<=n; j++){int k;
cin>>k;
a[i][j]=k;
a[j][i]=k;
}
}
int ans=0;
for (int i=1; i<=n; i++){sort(a[i]+1,a[i]+1+n);
if (a[i][n-1] >ans){ans=a[i][n-1];
}
}
cout<<1< LGP1007
解题思路（参考了相关题解）
两者相遇均调头 等价于 两者相遇后仍按照原先位置前行。
比如一个士兵位于坐标3，方向向右，那么两秒后，不论他经过了多少士兵，都一定会有一个士兵在坐标5。
#includeusing namespace std;
const int maxn=5e3+5;
int a[maxn];
int main(){// freopen("LGP1007.in","r",stdin);
// freopen("LGP1007.out","w",stdout);
int L;
int n,k;
cin>>L;
cin>>n;
int maxn=0,minn=0;
for (int i=1; i<=n; i++){cin>>k;
maxn=max(max(L-k+1,k),maxn);
minn=max(min(L-k+1,k),minn);
}
cout< 注意：max和min的使用要分清楚，min用于一个人两个方向上的最小值，而最后要保证所有人都要通过，所以又要取max。
LGP1223
解题思路显然需要将节水时间更短的人放在前面，这样人数能更快地减少，能使得最后平均节水时长最小。
#includeusing namespace std;
const int maxn=1e3+5;
double sum,cnt;
int n;
struct node{int t;
int num;
}a[maxn];
bool cmp(node x,node y){return x.tcin>>n;
for (int i=1; i<=n; i++){scanf("%d",&a[i].t);
a[i].num=i;
// sum+=a[i];
}
sort(a+1,a+1+n,cmp);
for (int i=1; i<=n; i++){cnt+=a[i].t*(n-i);
}
for (int i=1; i<=n; i++){printf("%d ",a[i].num);
}
printf("\n%.2lf",double(cnt)/n);
//system("pause");
return 0;
} LGP1090
解题思路显然每次要先将和最小的两组合并，这样的结果才是最优的。数据较大，需要用priority_queue进行每次首元素的读取和push。同时注意开long long。
#includeusing namespace std;
typedef long long ll;
priority_queue, greater>q;
const int maxn=1e4+5;
int n;
ll ans;
int main(){cin>>n;
int k;
for (int i=1; i<=n; i++){scanf("%d",&k);
q.push(k);
}
while (q.size()>1){ll tmp;
tmp=q.top();
q.pop();
tmp+=q.top();
q.pop();
q.push(tmp);
ans+=tmp;
}
cout< 彩蛋：
如果要求合并的两组要相连，就是需要用区间DP的合并石子了。
LGP1803
解题思路贪心思想，对于每个时间段都可视为一个线段，那么尽可能去使得线段右端点越小越好。这样对于后面的线段选择与否影响更小，故必然就是最优解。
#includeusing namespace std;
int n;
struct node{int l,r;
};
vectort;
bool cmp(node a,node b){return (a.rcin>>n;
for (int i=0; inode tmp;
cin>>tmp.l>>tmp.r;
t.push_back(tmp);
}
sort(t.begin(),t.end(),cmp);
int lt=-1,ans=0;
for (int i=0; iif (t[i].l >= lt){ans++;
lt=t[i].r;
}
}
cout< 本题可以不用vector笔者只是单纯想来练习其使用
注意vector的使用：
1.vector与结构体结合使用时，要注意读入的时候，需要用一个node tmp，读到tmp中，再a.push_back(tmp)即可；
2.push_back是从0开始的，所以之后调用应注意从0到n-1；
3.vector排序：sort(a.begin(),a.end(),cmp).
LGP1031
解题思路对于2~N-1的纸牌堆，都可以选择移动到左边或右边，这样两个方向较难进行模拟。所以可视为都向右边移动，并且移动的牌数可以为负数（相当于原本向左移动纸牌），如果当前牌数达到了平均值就continue，否则就把多的数值或者少的数值移动给右边的纸牌堆。
#includeusing namespace std;
const int maxn=1e2+5;
int a[maxn];
int main(){int n;
cin>>n;
int sum=0;
for (int i=1; i<=n; i++){cin>>a[i];
sum+=a[i];
}
int ave=sum/n;
int cnt=0;
for (int i=1; i<=n; i++){if (a[i]!=ave){a[i]-=ave;
a[i+1]+=a[i];
cnt++;
}
}
cout< LGP1020
解题思路这题并不是原题普通的LIS，需要将时间复杂度降为O(nlogn)，并且还要计算该序列中LIS的最小个数。
对于问题一，可以用二分进行优化。f[cnt]表示该LIS中有cnt个数时最后一个数字的大高度。对于每一个a[i]进行判断，如果a[i]小于当前大序列的最后一个数字高度，那么就可以cnt++，并将f[cnt]赋值为a[i]；否则，如果大于当前大序列的最后一个数字高度，就需要从前面的序列去寻找，即存在一个f[x]，x为1到cnt中某个数，能使得f[x]大于a[i]，同时f[x+1]小于a[i]，那么f[x+1]就是当前a[i]需要加入的序列。
对于问题二，很类似问题一，也可以用二分进行优化。f[cnt]表示第cnt个系统中最小导弹的高度，同时保证f[ ]数组的单调递增，也就是f[1]到f[cnt]都是单增的。那么对于每一次的a[i]都可以进行判断，如果a[i]大于f[cnt]，也就是没有系统拦截当前的导弹，就需要f[++cnt]=a[i]；反之，如果小于，那就二分寻找合适的高度。
#includeusing namespace std;
const int maxn=1e5+5;
vectora;
int n;
int f[maxn],v[maxn];
int main(){int k;
while (scanf("%d",&k)!=EOF){a.push_back(k);
}
n=a.size();
memset(f,0x3f,sizeof(f));
int cnt=0;
for (int i=0; iif (a[i]<=f[cnt]){f[++cnt]=a[i];
}
else {int l=1,r=cnt;
while (1){int mid=l+r>>1;
if (f[mid]>=a[i] && f[mid+1]break;
}
if (f[mid]>=a[i]){l=mid+1;
}
else if (f[mid]r=mid-1;
}
}
int mid=l+r>>1;
f[mid+1]=a[i];
}
}
memset(f,0,sizeof(f));
int ans=0;
for (int i=0; iif (a[i]>f[ans]){f[++ans]=a[i];
}
else {int l=1,r=ans;
while (1){int mid=l+r>>1;
if (f[mid]=a[i]){break;
}
if (f[mid]>=a[i]){r=mid-1;
}
else if (f[mid]l=mid+1;
}
}
int mid=l+r>>1;
f[mid+1]=a[i];
}
}
cout< 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧