P1086 [NOIP2004 普及组] 花生采摘

乍看还以为是个搜索，dfs都打好了，用个样例一输出发现不对，这第二个样例我输出的时间比较长大概花了几秒钟，并且这还不是最大规模，于是重新读题，然后发现似乎可以用贪心来做注释见代码

#include <bits/stdc++.h>
using namespace std;
int n,m,k,top;
int ans;
int mp[200][200];
struct g{
    int x,y,peanut;bool operator<(const g&rhs)const{
    return peanut>rhs.peanut;}
}a[500];
int main()
{
    ios::sync_with_stdio(false);cin>>n>>m>>k;for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
    cin>>mp[i][j];if(mp[i][j]){
    a[top].x = i;a[top].y=j;a[top++].peanut = mp[i][j];//放进数组}}}sort(a,a+top);//列个优先级int sum=0,wast=0;int x=-1,y=a[0].y;//选个好位置int wx,wy;for(int i=0;i<top;i++){
    wast = 0;wx = a[i].x;wy = a[i].y;wast = abs(x-wx)+abs(y-wy);/* cout<<wast<<endl; *///测试用的k--;k-=wast;if(k>=wx+1)//如果时间够就拿花生{
    ans+=mp[wx][wy];x = wx;y = wy;/* cout<<ans<<k<<endl; */}else{
    //不够就直接输出这个解cout<<ans<<endl;return 0;}}cout<<ans;return 0;
}