UPC 1336、1351、1353、1631、2655_综合

upc
输入样例

输出样例

主要是贪心思想，以结束时间从小到大排序。

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
#define l first
#define r second
const int N=110;
bool cmp(PII a,PII b)
{
    return a.r<b.r;
}
int main(void)
{
    int n;while(~scanf("%d",&n),n){
    PII s[N];int res=0,temp=0;for(int i=0;i<n;i++)scanf("%d%d",&s[i].l,&s[i].r);sort(s,s+n,cmp);for(int i=0;i<n;i++){
    if(s[i].l>=temp){
    res++;temp=s[i].r;}}cout<<res<<endl;}
}

在这里插入图片描述
主要是双指针算法。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
int main(void)
{
    int T;cin>>T;while(T--){
    int v,n;scanf("%d%d",&v,&n);int w[N];for(int i=0;i<n;i++) scanf("%d",&w[i]);sort(w,w+n);int l=0,r=n-1,res=0;int temp=w[l];while(l<=r){
    if(temp+w[r]>v) r--,res++;else{
    res++;r--;l++;}}cout<<res<<endl;}
}

在这里插入图片描述
刚开始以为是dp，后来看能分割。就是典型的贪心，先选价值大的。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
typedef pair<int,int> PII;
#define v first 
#define w second
bool cmp(PII a,PII b)
{
    return a.v>b.v;
}
int main(void)
{
    int T;scanf("%d",&T);while(T--){
    int n,V;scanf("%d%d",&n,&V);PII k[N];for(int i=0;i<n;i++)scanf("%d%d",&k[i].v,&k[i].w);sort(k,k+n,cmp);int res=0,i=0;while(V){
    if(V>=k[i].w){
    res+=k[i].w*k[i].v;}else{
    res+=k[i].v*V;	break;}V-=k[i].w;i++;}cout<<res<<endl;}
}

在这里插入图片描述
这个看起来很有值得讨论的地方。
首先我们可以根据辗转相除法可以求出n,n+1的最大公约数为1所以呢，相邻的两个数公约数一定是1，那么最有可能产生公约数大于1的地方就是n,n+2,用辗转相除法发现，要是奇数一定最大公约数为1（相邻的奇数最大公约数为1），偶数最大公约数一定是2（不会有更大的了），然后这就出来了要是偶数我们就不选最大的三个数因为出现了最大公约数，我们要选互质最大，只能选n*(n-1)(n-3),但是我们好像也发现一个问题，就是要是n%3==0,n-3也必然被3整除，我们要选再下一位，再下一位就是n-4也是偶数，所以再选下一位n-5,就变成了n(n-1)(n-5),一看不大靠谱，我们是不是可以选择(n-1) (n-2)(n-3),这个可以证明后者比较大的，（同时除以n-1,左边是n²-5n,右边是n²-5n+6)
思路就出来了，代码如下。

#include<iostream>
using namespace std;
int main(void)
{
    long long n,res;cin>>n;if(n&1) res=n*(n-1)*(n-2);else{
    if(n%3==0)res=(n-1)*(n-2)*(n-3);elseres=n*(n-1)*(n-3);}cout<<res;
}

2655
在这里插入图片描述
这个很有难度，我们枚举每个点能不能作为最小的距离试一下。有点枚举了，然后再贪心。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=1e6+10;
int x[N],y[N],ans[N],l[N];
int main(void)
{
    int n;cin>>n;memset(l,0x3f3f3f3f,sizeof l);for(int i=1;i<=n;i++)cin>>x[i]>>y[i];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
    for(int k=1;k<=n;k++)ans[k]=abs(x[k]-x[i])+abs(y[k]-y[j]);sort(ans+1,ans+n+1);int sum=0;for(int k=1;k<=n;k++){
    sum+=ans[k];l[k]=min(l[k],sum);	}}for(int i=1;i<=n;i++)cout<<l[i]<<endl;
}

在这里插入图片描述
查重？？我也很无奈。